Submission

Score: 0

User: Test

Problemset: ย่องเบาหลบกับระเบิด

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-17 14:14:45

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<char>> grid;
vector<vector<char>> grid2;
int dr[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dc[] = {0, 0, -1, 1, -1, 1, -1, 1};
void water(int i,int j){

    for(int x=0;x<8;x++){
        int ni = i+dr[x];
        int nj = j+dc[x];
        if(ni>=0 && nj>=0 && ni<n && nj<m){
            grid2[ni][nj]='0';
        }
    }
}
vector<vector<int>> dist;
int shortest_path(){
    queue<pair<int,int>> q;

    //?ش????? fix j ??Ѻ i
        for(int i=0;i<n;i++){
            if(grid2[i][0]!='0'){
                q.push({i,0});
                dist[i][0]=1;
            }
        }

    while(!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        //?礨ش?? ??ҵ?Ƿ????Ժ?͡?????????ش???? (n-1) ????Ҷ֧????
        if(c == m-1) return dist[r][c];

        //?Թ 4 ???
        for(int x = 0; x < 4; x++){
            int nr = r + dr[x];
            int nc = c + dc[x];

            if(nr >= 0 && nc >= 0 && nr < n && nc < m){
                if(grid2[nr][nc] != '0' && dist[nr][nc] == -1){
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }
    }
    return -1;
}


int main(){
    cin >> n >> m;
    grid.assign(n, vector<char>(m)); //*****
    grid2.assign(n, vector<char>(m)); //*****
    dist.assign(n, vector<int>(m,-1));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> grid[i][j];
        }
    }
    grid2=grid;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]=='0'){
                water(i,j);
            }
        }
    }
    shortest_path();
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }*/
    int mx = -1;
    for(int x=0;x<n;x++){
        mx=max(mx,dist[x][m-1]);
    }
    cout << mx;
}
/*
10 10
0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
*/
/*
5 5
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
*/