Submission

Score: 100

User: boomm

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

Language: cpp

Time: 0.113 second

Submitted On: 2026-03-12 22:21:00

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	int dx[4]={0,0,-1,1};
	int dy[4]={-1,1,0,0};
	vector<vector<int> > v(n,vector<int>(m));
	for(int i=0;i<n;i++){ 
		for(int j=0;j<m;j++){
			cin >> v[i][j];
		}
	}
	vector<pair<int,int> > isus;
	for(int i=0;i<n;i++){ 
		for(int j=0;j<m;j++){
			if(v[i][j]==0) isus.push_back({i,j});
		}
	}
	for(int j=0;j<isus.size();j++){
		int dx[8]={0,0,-1,-1,-1,1,1,1};
		int dy[8]={-1,1,-1,0,1,-1,0,1};
		for(int i=0;i<8;i++){
			int nx=isus[j].first+dx[i];
			int ny=isus[j].second+dy[i];
			if(nx>=0 && ny>=0 && nx<n && ny<m){
				v[nx][ny]=0;
			}
		}
	}
	queue<pair<int,int> > q;
	vector<vector<bool> > ch(n,vector<bool>(m,false));
	for (int i = 0; i < n; i++) {
        if (v[i][0]!=0){
        	ch[i][0]=true;
            q.push({i,0});
        }
    }
	int mn=1e9;
	int c=1;
	
	while(!q.empty()){
		int z=q.size();
		while(z--){
			int x=q.front().first;
			int y=q.front().second;
			q.pop();
			if(y==m-1){
				cout << c;
				return 0;
			}
			for(int k=0;k<4;k++){
				int nx=x+dx[k];
				int ny=y+dy[k];
				if(nx>=0 && ny>=0 && nx<n && ny<m && !ch[nx][ny] && v[nx][ny]==1){
					ch[nx][ny]=true;
					q.push({nx,ny});
				}
			}
		}
		c++;
	}
	if(mn==1e9) cout << "-1";
	else cout << mn;

	return 0;
}