Olya and Energy Drinks [Codeforces Round #442 D]

http://codeforces.com/contest/877/problem/D

縦N,横Mの盤面がある。
'.'が道で'#'が壁。
最初は(x1,y1)にいる。
各ターン上下左右いずれかに1～Kマス分直進できる。
なお、壁は通れない。
(x2,y2)まで最短で何ターンかかるか。

N,M≦10^3
K≦10^3

解法

http://codeforces.com/contest/877/submission/31653201

BFSで解く。
よくある幅優先をそのままやるだけなのだが、以下のことに注意しながら枝刈りしつつ書く。
　
上下左右にKマスだけ進む最中に…

• 壁があったら中断(あたりまえ)
• もう既にBFSしたマスに到達したら中断(そこより先のそのマスのBFSでチェックしてある)
• 1度queueに入れたことのあるやつは再度入れない

　
これで最悪ケースを考えても、O(10^9)だけど定数が大分軽そうなので通るかと思って出すと通る。

#define INF INT_MAX/2
int H, W,K, x1, yy1, x2, y2;
string B[1010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int vis[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    rep(y, 0, H) cin >> B[y];
    cin >> yy1 >> x1 >> y2 >> x2;
    x1--; yy1--; x2--; y2--;

    rep(y, 0, H) rep(x, 0, W) vis[y][x] = INF;
    vis[yy1][x1] = 0;

    queue<int> que;
    que.push(yy1 * 1010 + x1);

    while (!que.empty()) {
        int q = que.front(); que.pop();
        
        int x = q % 1010;
        int y = q / 1010;
        int c = vis[y][x];

        //printf("[%d %d]\n", x, y);

        if (x == x2 and y == y2) {
            printf("%d\n", c);
            return;
        }

        rep(d, 0, 4) {
            int xx = x, yy = y;
            rep(i, 0, K) {
                xx += dx[d];
                yy += dy[d];
                if (0 <= xx and xx < W and 0 <= yy and yy < H) {
                    if (B[yy][xx] == '#' or vis[yy][xx] <= c) break;
                    if (B[yy][xx] == '.' and vis[yy][xx] == INF) {
                        vis[yy][xx] = c + 1;
                        que.push(yy * 1010 + xx);
                    }
                }
                else break;
            }
        }
    }

    printf("-1\n");
}