[AtCoder] ABC 176 D – Wizard in Maze

2020年8月23日2020年12月14日

問題

方針

領域の作成

徒歩で行くことができるマスをグループ化し、IDを振ります。マス \( (i, j) \) の ID が \( 0\) であることを \( G(i, j) = 0 \) と表し、そのマスから徒歩でいけるマスの ID は \( 0\) となります。 これらは幅優先探索で求めることができます。

隣接リストの作成

道であるマス \( (i, j) \) から \( |i + x| \leq 2 \wedge |i + y| \leq 2 \) を満たす \( x, y\) について、マス \( (i + x, j + y) \) が道であるときワープ魔法で移動することができます。このとき、\( G(i, j) \neq G(i + x, j + y) \) であれば辺として追加します。

隣接リストの探索

隣接リストが作成できたら、\( G(C_w, C_h) \) から探索し、\( G(D_w, D_h) \) までの最短距離を調べます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int H, W, C_h, C_w, D_h, D_w;
    cin >> H >> W >> C_h >> C_w >> D_h >> D_w;
    C_h--;
    C_w--;
    D_h--;
    D_w--;
    char S[H][W];
    for (int i = 0; i < H; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < W; j++) {
            S[i][j] = s[j];
        }
    }
    int MAX = 100000000;
    int G[H][W];
    
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            G[i][j] = -1;
        }
    }
    
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    deque<pair<int, int>> q;
    int idx = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (G[i][j] == -1 && S[i][j] == '.') {
                G[i][j] = idx;
                vector<pair<int, int>> v;
                q.push_back(make_pair(i, j));
                while (!q.empty()) {
                    pair<int, int> p = q.front();
                    q.pop_front();
                    int x = p.second;
                    int y = p.first;
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                        if (S[ny][nx] == '.' && G[ny][nx] == -1) {
                            G[ny][nx] = idx;
                            q.push_back(make_pair(ny, nx));
                        }
                    }
                }
                idx++;
            }
        }
    }
    
    int ex[] = {1, 1, -1, -1, 2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2};
    int ey[] = {1, -1, 1, -1, -2, -1, 0, 1, 2, 2, -2, 2, -2, 2, -2, 2, 1, 0, 1, 2};
    set<int> adj[idx];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (G[i][j] == -1) continue;
            for (int k = 0; k < 20; k++) {
                int nx = j + ex[k];
                int ny = i + ey[k];
                if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                if (S[ny][nx] == '.' && G[i][j] != G[ny][nx]) {
                    adj[G[i][j]].insert(G[ny][nx]);
                    adj[G[ny][nx]].insert(G[i][j]);
                }
            }
        }
    }

    int L[idx];
    for (int i = 0; i < idx; i++) {
        L[i] = MAX;
    }
    L[G[C_h][C_w]] = 0;
    deque<int> dq;
    dq.push_back(G[C_h][C_w]);
    while (!dq.empty()) {
        int p = dq.front();
        dq.pop_front();
        for (int i : adj[p]) {
            if (L[p] + 1 < L[i]) {
                L[i] = L[p] + 1;
                dq.push_back(i);
            }
        }
    }

    if (L[G[D_h][D_w]] != MAX) {
        cout << L[G[D_h][D_w]] << "\n";
    } else {
        cout << "-1\n";
    }
    return 0;
}