Submission

Score: 100

User: Nay-O

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

Language: cpp

Time: 0.062 second

Submitted On: 2026-03-26 13:35:43

#include<bits/stdc++.h>
using namespace std;
using pii = array<int,3>;

bool vis[1005][1005];

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int n,m; cin>>n>>m;
	
	int arr[n][m];
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin>>arr[i][j];
		}
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(arr[i][j]!=0) continue;
			for(int a = i-1;a<=i+1;a++){
				for(int b = j-1; b<=j+1;b++){
					if(a<0||a>n-1||b<0||b>m-1||arr[a][b]==0) continue;
					arr[a][b]=2;
				}
			}
		}
	}
	
	queue<pii> q;
	
	for(int i = 0; i < n; i++){
		q.push({i,0,1});
	}
	
	
	while(!q.empty()){
		int a = q.front()[0], b = q.front()[1], c = q.front()[2];
		q.pop();
		if(b==m-1){
			cout << c;
			return 0;
		}
		for(int i = 0; i < 4; i++){
			int yy = a+dy[i],xx=b+dx[i];
			if(yy<0||yy>n-1||xx<0||xx>m-1||vis[yy][xx]||arr[yy][xx]!=1) continue;
			vis[yy][xx]=true;
			q.push({yy,xx,c+1});
		}
	}
	
	cout << -1;
	
	return 0;
}