Submission #71676610

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
using P = pair<int, int>;

int h,w;
bool valid(int i, int j) {return 0 <= i && i < h && 0 <= j && j < w;}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
    cin >> h >> w;
    string S[h];
    for(int i = 0; i < h; i++) cin >> S[i];
    
    vector<bool> visited(26, false);
    vector<vector<P>> idx(26);
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if('a' <= S[i][j] && S[i][j] <= 'z'){
                idx[S[i][j]-'a'].push_back({i,j});
            }
        }
    }

    queue<P> que;
    vector<vector<int>> dist(h, vector<int>(w, -1));

    que.push({0,0});
    dist[0][0] = 0;

    while(!que.empty()){
        auto [x,y] = que.front();
        que.pop();

        for(int k = 0; k < 4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(valid(nx, ny) && S[nx][ny] != '#' && dist[nx][ny] == -1){
                que.push({nx, ny});
                dist[nx][ny] = dist[x][y] + 1;
            }
        }

        if('a' <= S[x][y] && S[x][y] <= 'z' && visited[S[x][y]] == false){
            for(auto [nx, ny] : idx[S[x][y]-'a']){
                if(dist[nx][ny] == -1){
                    que.push({nx, ny});
                    dist[nx][ny] = dist[x][y] + 1;
                }
                visited[S[x][y]] = true;
            }
        }
    }

    cout << dist[h-1][w-1] << endl;
}

Submission Info

Judge Result