Submission

Score: 0

User: hmmm

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

Language: cpp

Time: 0.036 second

Submitted On: 2025-07-22 10:41:33

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,2>;
const int N=1005;
int a[N][N];
bool chk[N][N];
queue<pii> q;
int vis[N][N];
int dx[]={0,0,1,1,1,-1,-1,-1};
int dy[]={1,-1,0,1,-1,0,1,-1};

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==0){
				for(int k=0;k<8;k++){
					chk[i+dx[k]][j+dy[k]]=true;
				}
			}
			
		}
	}
	memset(vis,0x3f,sizeof vis);
	for(int i=1;i<=n;i++){
		if(!chk[i][1]){
//			cout << i << ' ';
			q.push({i,1});
			vis[i][1]=1;
		}
	}
	while(!q.empty()){
		auto x=q.front()[0];
		auto y=q.front()[1];
		q.pop();
		if(x<1 || y<1 || x>n || y>m) continue;
//		cout << x << ' ' << y << "\n";
		if(y==m){
			cout << vis[x][y];
			return 0;
		}
		if(vis[x][y+1]>vis[x][y]+1 && !chk[x][y+1]){
			vis[x][y+1]=vis[x][y]+1;
			q.push({x,y+1});
		}
		if(vis[x-1][y]>vis[x][y]+1 && !chk[x-1][y]){
			vis[x-1][y]=vis[x][y]+1;
			q.push({x-1,y});
		}
		if(vis[x+1][y]>vis[x][y]+1 && !chk[x+1][y]){
			vis[x+1][y]=vis[x][y]+1;
			q.push({x+1,y});
		}
	}
	cout << "-1";
}