Submission

Score: 0

User: Pxnny

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

Language: cpp

Time: 1.085 second

Submitted On: 2026-03-20 15:34:25

#include <bits/stdc++.h>
using namespace std;
#define piii pair<pair<int, int>, int>


vector<vector<int>> grid(1005, vector<int>(1005)), cgrid(1005, vector<int>(1005));
int n, m;
vector<int> ct;
int yy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
int xx[] = {0, -1, 1, 0, 1, -1, 1, -1};

void mark(int y, int x){
    for(int i=0; i<8; i++){
        int ny = y + yy[i];
        int nx = x + xx[i];
        if(ny <0 || ny>=n || nx<0 || nx>=m) continue;
        grid[ny][nx] = 0;
    }
}
    

void floodfill(int yi, int xi){
    queue<piii> q;
    q.push({{yi, xi}, 1});

    while(!q.empty()){
        int y = q.front().first.first;
        int x = q.front().first.second;
        int t = q.front().second;
        q.pop();

        if(grid[y][x] == 0)continue;
        grid[y][x] = 0;
        //cout << y << " "<< x << " " << t << endl;
        if(x == m-1){
            ct.push_back(t);
            return;
        }

        for(int i=0;i <4; i++){
            int ny = y + yy[i];
            int nx = x + xx[i];
            if(ny <0 || ny>=n || nx<0 || nx>=m) continue;
            if(grid[ny][nx] == 0) continue;
            q.push({{ny, nx}, t+1});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> grid[i][j];
            cgrid[i][j] = grid[i][j];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(cgrid[i][j] == 0){
                mark(i, j);
            }
        }
    }
     /*for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << grid[i][j];
        }
        cout << endl;
    }*/
    cgrid = grid;
    for(int i=0; i<n; i++){
        grid = cgrid;
        if(grid[i][0] != 0){
            //cout << grid[i][0]<< endl;
            //cout << i << endl;
            floodfill(i, 0);
        }
     }
    /*for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << grid[i][j];
        }
        cout << endl;
    }*/
   if(ct.size() == 0){
        cout << -1;
        return 0;
   }
   sort(ct.begin(), ct.end());
   cout << ct[0];
}
/*
5 5
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


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

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

3 3
1 1 1
1 0 1
1 1 1

*/