Submission

Score: 100

User: nemuchannnUwU

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

Language: cpp

Time: 0.050 second

Submitted On: 2026-10-06 19:07:23

#include<bits/stdc++.h>
using namespace std;
int dx[]={1,-1,0,0,-1,1,1,-1};
int dy[]={0,0,1,-1,1,1,-1,-1};

int _canx[]={0,0,1,-1};
int _cany[]={-1,1,0,0};
bool chk(int x,int y,int n,int m){
	return (x>=0&&x<n&&y>=0&&y<m);
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	int n,m; cin >> n >> m;
	int mn=INT_MAX;
	vector<vector<int>> grid(n,vector<int>(m));
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			cin >> grid[i][j];
		}
	}
	vector<vector<int>> block=grid;
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			if (grid[i][j]==0){
				for (int k=0;k<8;k++){
					int nx=i+dx[k];
					int ny=j+dy[k];
					if (chk(nx,ny,n,m)){
						block[nx][ny]=0;
					}
				}
			}
		}
	}
	vector<vector<bool>> visited(n,vector<bool> (m,false));
	queue<tuple<int,int,int>> q;
	for (int i=0;i<n;i++){
		if (block[i][0]==0) continue;
		q.push({i,0,1});
		visited[i][0]=true;
	}
	
	while(!q.empty()){
		auto [x,y,dist]=q.front();
		q.pop();
	
		if (y==m-1){
			mn=min(dist,mn);
			break;
		}
		for (int j=0;j<4;j++){
			int nx=x+dx[j];
			int ny=y+dy[j];
			if (chk(nx,ny,n,m)&&!visited[nx][ny]&&block[nx][ny]!=0){
				visited[nx][ny]=true;
				q.push({nx,ny,dist+1});	
			}
		}
	}
	if (mn==INT_MAX) cout << "-1";
	else cout << mn;
	
}