Submission

x-P-P--P

Score: 39

User: Jibhong

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.003 second

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

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

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

vector <string> grid;
queue <cell> floodq;
bool visited [110][110];

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

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

    int mindist=2e9;
        
    while(!floodq.empty()){

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

        if(visited[lastcell.x][lastcell.y])continue;
        visited[lastcell.x][lastcell.y]=1;

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

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

    cout<<mindist;

    return 0;
}