Submission

[PPPPPPP]

Score: 100

User: Monasm

Problemset: Sirabyrinth 5

Language: cpp

Time: 0.053 second

Submitted On: 2024-11-22 22:52:55

#include <bits/stdc++.h>

using namespace std;

int gx[] = {1,-1,0,0};
int gy[] = {0,0,-1,1};

int main(){
    int n,m,sx,sy;cin>>n>>m;
    queue<pair<int,int>> q;
    vector<vector<char>> adj(n,vector<char>(m));
    vector<vector<int>> dist(n,vector<int>(m,1e9));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>adj[i][j];
            if(adj[i][j]=='E'){
                q.push({i,j});
                dist[i][j]=0;
            }
            if(adj[i][j]=='S'){
                sx=i;sy=j;
            }
        }
    }
    int cnt=0;
    while (!q.empty()) {
        int nx = q.front().first, ny = q.front().second;
        q.pop();
        for(int i=0;i<4;i++) {
            int x=nx+gx[i],y=ny+gy[i];
            if (x>=0&&x<n&&y>=0&&y<m&&adj[x][y]!='#'&&dist[x][y]>dist[nx][ny]+1) {
                q.push({x, y});
                dist[x][y] = dist[nx][ny] + 1;
            }
        }
    }
    int d = dist[sx][sy],ans = d+1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(adj[i][j]>='1'&&adj[i][j]<='9'&&dist[i][j]<=d){
                ans+=adj[i][j]-'0';
            }
        }
    }
    cout<<ans;
}