https://atcoder.jp/contests/abc170/tasks/abc170_f

解説

https://atcoder.jp/contests/abc170/submissions/14369162

後追いで解いて、色々な解法を目にしてしまったので、以下にまとめておく。
3種類見かけた。
難易度はどれもどれという感じもしているので、全部見てみるといい。

1. 公式解説解法
拡張ダイクストラをする。
状態を(x座標, y座標, 向いている方向)とする。
そして移動するのだが、移動コストは一律1/Kとしておく。
これで遷移させていくのだが、向いている方向を変えるときに、コストを切り上げしてから遷移させる。
これだけではよくわからないと思うのだが、コストが整数になっていないうちは、Kマスの直線の移動中であると考える。
なので、方向が変わったときにコストを切り上げるのは、
方向を変える地点をKマス移動の終着点として確定させることを意味する。
この点だけ理解すれば、あとは拡張ダイクストラをすると答えが導ける。
1/Kと小数になるのは色々大変なので、全体をK倍して、コストの切り上げはコストを
最も近いKの倍数に揃えるようにすればいいだろう。
O(HWlog(HW))

2. Chokudaiさん解法
実装が最も簡単。
普通にBFSをまず書く。
Kマス移動も普通に書く（ただし全部コストは1にする）。
すると、O(HWK)になると思う。

これに自明な枝刈りだけを加える。
ある座標からKマス移動するときに既に訪問済みの座標があったら、それ以降の移動は枝刈りすることができる。
ただし、同じコストを書き込もうとしたときだけ通り抜けて続けさせる。
同じコスト以外（より小さいコストが書かれている）なら確実にもっと良い行動をそれ以降に続けることができるが、
同じコストなら分からない。
なので、同じコスト以外は自明に枝刈りができることになる。

正直、厳密にはこれでなぜ通るかは自分にはわからないのだが、直感的・実験的に正しそうな感じはする。
（この同じコストを書き込もうとした時というのはあまりなさそうな雰囲気はある）
なので、Kマス移動させていって、適切に枝刈りで移動をやめれば、間に合う。

3. set解法
BFSで計算量がO(HW)になるのは、訪れていない頂点だけを探索するようにしているからである。
これを忠実に拡張させたset解法がある。
列・行毎に「まだ訪れていない座標」をsetで管理しておく。
これで縦横にKマス移動するときに、ある座標からKマス移動したときに、
まだ訪れていない頂点が何であるかは、setを使えば高速に見つけ出すことができる。
その見つけた頂点にだけ遷移を絞れば、訪れていない頂点だけを探索するようにできる。
setを使うので、その分だけ計算量が悪化して、O(HWlog(H+W))となる。

自分はサボって一番実装が簡単なchokudaiさん解法で通した。
どの解法で解いても何かしらの力がつきそうである。

int H, W, K, sx, sy, tx, ty;
string c[1010101];
int mi[1010101];
bool vis[1010101];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K >> sx >> sy >> tx >> ty;
    rep(y, 0, H) cin >> c[y];
    sx--; sy--; tx--; ty--;

    queue<int> que;
    rep(i, 0, 1010101) mi[i] = inf;

    que.push(sx * W + sy);
    vis[sx * W + sy] = true;
    mi[sx * W + sy] = 0;

    while (!que.empty()) {
        int q = que.front(); que.pop();

        int x = q / W;
        int y = q % W;

        if (x == tx && y == ty) {
            printf("%d\n", mi[q]);
            return;
        }

        rep(d, 0, 4) {
            int xx = x, yy = y;
            rep(k, 0, K) {
                xx += dx[d];
                yy += dy[d];

                if (xx < 0 || H <= xx || yy < 0 || W <= yy) break;
                if (c[xx][yy] == '@') break;
                
                int id = xx * W + yy;
                if (vis[id] && mi[q] + 1 != mi[id]) break;

                if (!vis[id]) {
                    vis[id] = true;
                    mi[id] = mi[q] + 1;
                    que.push(id);
                }
            }
        }
    }

    printf("-1\n");
}

はまやんはまやんはまやん

hamayanhamayan's blog

Pond Skater [AtCoder Beginner Contest 170 F]

解説