Submission

Score: 100

User: tha_smith

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

Language: cpp

Time: 0.045 second

Submitted On: 2026-03-07 19:38:55

#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005],N,M,n,d[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
bool vis[1005][1005],grid[1005][1005];
queue<pair<int,int>> q;

int main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> N >> M;
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=M; j++) {
			cin >> n;
			if(n==0) {
				grid[i][j] = grid[i-1][j-1] = grid[i-1][j] = grid[i-1][j+1] = grid[i][j-1] = grid[i][j+1] = grid[i+1][j-1] = grid[i+1][j] = grid[i+1][j+1] = 1;
				vis[i][j] = vis[i-1][j-1] = vis[i-1][j] = vis[i-1][j+1] = vis[i][j-1] = vis[i][j+1] = vis[i+1][j-1] = vis[i+1][j] = vis[i+1][j+1] = 1;
			}
		}
	}
	for(int i=1; i<=N; i++) {
		if(grid[i][1])
			continue;
		q.push({i,1});
		vis[i][1]=1;
	}
	while(!q.empty()) {
		auto[x,y] = q.front();
		q.pop();
		for(int k=0; k<4; k++) {
			int nx = x+d[k][0];
			int ny = y+d[k][1];
			if(nx<1 || ny<1 || nx>N || ny>M)
				continue;
			if(vis[nx][ny] || grid[nx][ny])
				continue;
			vis[nx][ny]=1;
			dp[nx][ny] = dp[x][y]+1;
			q.push({nx,ny});
		}
	}
	int ans = INT_MAX;
	for(int i=1; i<=N; i++) {
		if(dp[i][M]==0)
			continue;
		ans=min(ans,dp[i][M]);
	}
	if(ans==INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans+1;
	}
}