Submission

Score: 100

User: Monasm

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.003 second

Submitted On: 2024-11-21 20:07:50

#include <bits/stdc++.h>

using namespace std;

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

int main(){
    int n,m;cin>>n>>m;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
    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]=='S'){
                pq.push({0,{i,j}});
                dist[i][j] = 0;
            }
        }
    }
    int ans=1e9;
    while(!pq.empty()){
        int d = pq.top().first;
        int nx = pq.top().second.first;
        int ny = pq.top().second.second;
        pq.pop();
        for(int i=0;i<4;i++){
            int x=gx[i]+nx,y=gy[i]+ny;
            if(!(0<=x&&x<n&&0<=y&&y<m)){
                continue;
            }
            if(adj[x][y] == '#'){
                if(dist[x][y]>d+1){
                    dist[x][y]=d+1;
                    pq.push({d+1,{x,y}});
                }
            }
            else if(adj[x][y] == '.'){
                if(dist[x][y]>d){
                    dist[x][y]=d;
                    pq.push({d,{x,y}});
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        ans=min(ans,dist[i][0]);
        ans=min(ans,dist[i][m-1]);
    }
    for(int i=0;i<m;i++){
        ans=min(ans,dist[0][i]);
        ans=min(ans,dist[n-1][i]);
    }
    cout<<ans;
}