Submission

Score: 0

User: boomm

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 21:47:17

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

void dfs(int x,int y,int n,int m,vector<vector<int> >& v){
	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=x+dx[i];
		int ny=y+dy[i];
		if(nx>=0 && ny>=0 && nx<n && ny<m){
			v[nx][ny]=0;
		}
	}
}
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];
		}
	}
	for(int i=0;i<n;i++){ 
		for(int j=0;j<m;j++){
			if(v[i][j]==0) dfs(i,j,n,m,v);
		}
	}
	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){
				mn=min(mn,c);
				break;
			}
			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;
}