Submission

P-PPP-PP

Score: 78

User: Jibhong

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.002 second

Submitted On: 2024-12-14 20:27:19

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

typedef struct cell{
    int x;
    int y;
    int dist;
}cell;

vector <string> grid;
queue <cell> floodq;
// int visited [110][110];
vector <vector <int>> visited(110,vector <int> (110, 2e9));
int mindist=2e9;

void print(int n,int m){
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(visited[i][j]==2e9)
                cout<<grid[j][i];
            else
                cout<<visited[i][j];
        }
        cout<<"\n";
    }
    cout<<mindist<<"\n";
    return;
}

void add_cell(cell nowcell,cell lastcell){
    if (grid[nowcell.y][nowcell.x]=='#')
        ++nowcell.dist;
    visited[lastcell.x][lastcell.y]=lastcell.dist;
    floodq.emplace(nowcell);
    return;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        string inp;
        cin>>inp;
        grid.emplace_back(inp);
        for(int j=0;j<n;++j){
            if(inp[j]=='S'){
                cell startcell = {j,i,0};
                floodq.emplace(startcell);
            }
        }
    }
        
    while(!floodq.empty()){


        cell lastcell=floodq.front();
        floodq.pop();

        if (lastcell.x==0 || lastcell.x==m || lastcell.y==0 ||lastcell.y==n){
            mindist=min(mindist,lastcell.dist);
        }

        if(visited[lastcell.x][lastcell.y]<=lastcell.dist)continue;
        visited[lastcell.x][lastcell.y]=lastcell.dist;
        // print(n,m);


        if (lastcell.x + 1 <  n && visited[lastcell.x + 1][lastcell.y] > lastcell.dist) {
            cell nowcell=lastcell;
            ++nowcell.x;
            add_cell(nowcell,lastcell);
        }
        if (lastcell.x - 1 >= 0 && visited[lastcell.x - 1][lastcell.y] > lastcell.dist) {
            cell nowcell=lastcell;
            --nowcell.x;
            add_cell(nowcell,lastcell);
        }
        if (lastcell.y + 1 <  m && visited[lastcell.x][lastcell.y + 1] > lastcell.dist) {
            cell nowcell=lastcell;
            ++nowcell.y;
            add_cell(nowcell,lastcell);
        }
        if (lastcell.y - 1 >= 0 && visited[lastcell.x][lastcell.y - 1] > lastcell.dist) {
            cell nowcell=lastcell;
            --nowcell.y;
            add_cell(nowcell,lastcell);
        }
    }

    cout<<mindist;
    // print(n,m);
    return 0;
}