Submission

Score: 100

User: hmmm

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

Language: cpp

Time: 0.055 second

Submitted On: 2025-07-22 10:43:45

#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,0,-1,1,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;
		}
		for(int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(vis[xx][yy]>vis[x][y]+1 && !chk[xx][yy]){
				vis[xx][yy]=vis[x][y]+1;
				q.push({xx,yy});
			}
		}
	}
	cout << "-1";
}