Submission

Score: 0

User: C12

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

Language: cpp

Time: 0.044 second

Submitted On: 2026-01-01 20:35:41

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

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define ll long long
#define ull unsigned long long
#define mp make_pair
 
#define mpiii(a,b,c) make_pair(a,make_pair(b,c));
// ll mod = 1000000007;

int board[1001][1001];
int view[1001][1001] = {0};

int posx[4] = {-1,1,0,0};
int posy[4] = {0,0,1,-1};

int nx,ny;

void solve(){
    int n,m;

    cin >> n >> m;

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> board[i][j];
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(board[i][j] == 0){
                for(int k = 0;k < 4;k++){
                    nx = i + posx[k];
                    ny = j + posy[k];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m){
                        continue;
                    }
                    board[nx][ny] = -1;
                }
            }
        }
    }

    queue<pii>q;
    int st;
    int cnt = 0;
    int x,y;

    for(int i = 0;i < n;i++){
        if(board[i][0] > 0){
            q.push(mp(i,0));
            view[i][0] = 1;
        }
    }

    while(1){
        st = q.size();
        cnt++;
        while(st--){
            x = q.front().first;
            y = q.front().second;
            q.pop();

            for(int k = 0;k < 4;k++){
                nx = x + posx[k];
                ny = y + posy[k];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m || view[nx][ny] || board[nx][ny] <= 0){
                    continue; 
                }
                view[nx][ny] = 1;
                q.push(mp(nx,ny));

                if(ny == m-1){
                    cout << (cnt + 1);
                    return;
                }
            }
        }
        if(q.empty()){
            cout << -1;
            return;
        }
    }

    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
 
    // cin >> q;

    // while(q--)
        solve(); 

    return 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

10 10
0 1 1 1 0 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1

10 10
1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 0 0 1
0 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1

*/