Submission

Score: 100

User: exoworldgd

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

Language: cpp

Time: 0.099 second

Submitted On: 2025-12-07 13:42:32

#pragma GCC optimize("O5,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
using namespace std;
const int inf=LLONG_MAX, N=1005, dx[]={-1,1,0,0},dy[]={0,0,-1,1},ddx[]={-1,-1,-1,0,0,1,1,1},ddy[]={-1,0,1,-1,1,-1,0,1};
int n,m,grid[N][N],safe[N][N],dist[N][N],ans=inf;
signed main(void){
	exoworldgd;
	cin >> n >> m,memset(dist,-1,sizeof(dist));
	for (int i=0; i< n; i++)for (int j=0 ; j< m; j++) cin >> grid[i][j];
	for (int i=0; i< n;i ++) {
		for (int j=0; j<m ;j++) {
			if (!grid[i][j]) {safe[i][j]=0; continue;}
			safe[i][j]=1;
			for (int k=0; k< 8; k++) {
				int nx=i+ddx[k], ny=j+ddy[k];
				if (nx>=0 && nx<n && ny>=0 && ny<m && !grid[nx][ny]) safe[i][j]=0;
			}
		}
	}
	queue<pair<int,int>> q;
	for (int i=0; i< n; i++) if (safe[i][0]) dist[i][0]=1, q.emplace(i,0);
	while (!q.empty()) {
		auto [x,y]=q.front(); q.pop();
		for (int i=0;i < 4;i ++) {
			int nx=x+dx[i], ny=y+dy[i];
			if (nx<0||nx>=n||ny<0||ny>=m||!safe[nx][ny]||dist[nx][ny]^-1) continue;
			dist[nx][ny]=dist[x][y]+1, q.emplace(nx,ny);
		}
	}
	for (int i=0; i<n ;i++) if (dist[i][m-1]^-1) ans=min(ans,dist[i][m-1]);
	cout << (ans==inf ? -1 : ans);
}