Submission

[PPxSSSSSS]

Score: 0

User: Monasm

Problemset: Sirabyrinth 5

Language: cpp

Time: 0.177 second

Submitted On: 2024-11-23 15:26:34

#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 size = q.size();
        for(int i=0;i<size;i++){
            int nx=q.front().first,ny=q.front().second;
            dist[nx][ny] = cnt;
            q.pop();
            for(int j=0;j<4;j++){
                int x=nx+gx[j],y=ny+gy[j];
                if(0<=x&&x<n&&0<=y&&y<m&&adj[x][y]!='#'&&dist[x][y]==1e9){
                    q.push({x,y});
                }
            }
        }
        cnt++;
    }
    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;
}