Submission

Score: 0

User: lobatza

Problemset: Sirabyrinth 5

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 05:37:48

#include <bits/stdc++.h>
using namespace std;

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

int main(){
    int n, m, sx, sy, d, ans; 
    cin >> n >> m;
    char adj[n][m];
    int dist[n][m];
    queue<pair<int,int>> q;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
        dist[i][j]=1e9;
        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;
    }
    while (!q.empty()) {
        auto [nx, ny] = q.front(); 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;
        }
    }
    d = dist[sx][sy], ans = d + 1;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) 
        if(isdigit(adj[i][j]) && dist[i][j] <= d) ans += adj[i][j] - '0';
    cout << ans;
}