【題解】AtCoder ABC 184E – Third Avenue

【題目敘述】https://atcoder.jp/contests/abc184/tasks/abc184_e

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int n, m, g[2005][2005], vis[30], dis[2005][2005], d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector <pair<int, int> > v[30];
pair<int, int> s, t;
string str;

int main(){
    cin >> n >> m;
    memset(g, -1, sizeof(g));
    memset(dis, -1, sizeof(dis));
    for (int i = 1; i <= n; i++){
        cin >> str;
        for (int j = 1; j <= m; j++){
            if (str[j-1] != '#') g[i][j] = 0;
            if (str[j-1] == 'S') s = {i, j};
            else if (str[j-1] == 'G') t = {i, j};
            else if ('a' <= str[j-1] && str[j-1] <= 'z'){
                //cout << "found " << str[j-1] << "\n";
                g[i][j] = str[j-1]-'a'+1;
                v[g[i][j]].push_back({i, j});
            }
        }
    }
    queue <pair<int, int> > q;
    q.push(s);
    dis[s.first][s.second] = 0;
    while (!q.empty()){
        int x = q.front().first, y = q.front().second;
        //cout << x << " " << y << " " << dis[x][y] << "\n";
        q.pop();
        for (int i = 0; i < 4; i++){
            int nx = x+d[i][0], ny = y+d[i][1];
            if (g[nx][ny] >= 0 && dis[nx][ny] == -1){
                dis[nx][ny] = dis[x][y]+1;
                q.push({nx, ny});
            }
        }
        if (g[x][y] > 0 && !vis[g[x][y]]){
            // << "jump!\n";
            vis[g[x][y]] = 1;
            for (auto i:v[g[x][y]]){
                int nx = i.first, ny = i.second;
                if (g[nx][ny] >= 0 && dis[nx][ny] == -1){
                    dis[nx][ny] = dis[x][y]+1;
                    q.push({nx, ny});
                }
            }
        }
    }
    cout << dis[t.first][t.second] << "\n";
}


分享本文 Share with friends