【ABC184】E - Third Avenue

atcoder.jp

解法

テレポートが使えなければ、BFSするだけで解ける。

テレポートを無制限に使用できるとすると大量の辺が追加されることになって、時間内に探索を完了するのが難しくなる。
そこで、同じ文字のテレポートは１回しか使用できないという制限を加えることにする。
あとは、BFSするだけで答えがもとまる。

なぜ制限を加えてもよいのか

同じ文字を使ったテレポートを２回するぐらいなら、最初からゴールに一番近い同じ文字に１回でテレポートすればよいため。

実装

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    REP (i, H) cin >> S[i];

         // テレポート先一覧
    vector<vector<pair<int, int>>> teleport(26);
         // 既にテレポートを使ったかどうか
    vector<bool> used(26, 0);
    int sy, sx, gy, gx;
    REP (i, H) {
        REP (j, W) {
            if (S[i][j] == 'S') {
                sy = i;
                sx = j;
            } else if (S[i][j] == 'G') {
                gy = i;
                gx = j;
            } else if (S[i][j] != '.' && S[i][j] != '#') {
                teleport[S[i][j] - 'a'].push_back({i, j});
            }
        }
    }

    vector<vector<int>> direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    vector<vector<long long>> dist(H, vector<long long>(W, INF64));
    queue<pair<int, int>> que;
    dist[sy][sx] = 0;
    que.push({sy, sx});
    
        // BFS
    while (!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
    
        for (int i = 0; i < 4; i++) {
            int ny = y + direction[i][0];
            int nx = x + direction[i][1];
    
            if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
            if (S[ny][nx] == '#' || dist[ny][nx] != INF64) continue;
    
            dist[ny][nx] = dist[y][x] + 1;
            que.push({ny, nx});
        }

        // テレポート
        int num = S[y][x]-'a';
                 // このif文で英小文字かどうかを判断できる
        if (num >= 0 && num < 26) {
            if (used[num]) continue;
            used[num] = true;

            REP (j, teleport[num].size()) {
                int ny = teleport[num][j].first;
                int nx = teleport[num][j].second;
                if (dist[ny][nx] == INF64) {
                    dist[ny][nx] = dist[y][x] + 1;
                    que.push({ny, nx});
                }
            }
        }
    }

    cout << (dist[gy][gx] == INF64 ? -1 : dist[gy][gx]) << endl;

    return 0;
}