Submission

[PPPPPPPPP]

Score: 100

User: Monasm

Problemset: Sirabyrinth 5

Language: cpp

Time: 0.095 second

Submitted On: 2024-11-26 16:07:16

#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];
    vector<pair<int,int>> e;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(adj[i][j]>='1'&&adj[i][j]<='9'){
                e.push_back({dist[i][j],adj[i][j]-'0'});
            }
        }
    }
    sort(e.begin(),e.end());
    for(auto i:e){
        if(i.first<=d){
            d+=i.second;
        }
    }
    cout<<d+1;
}