Submission

Score: 0

User: tha_smith

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

Language: cpp

Time: 0.048 second

Submitted On: 2026-02-28 16:21:27

#include <bits/stdc++.h>
using namespace std;
int grid[1005][1005],dp[1005][1005],vis[1005][1005],N,M,n,d[4][2]={{0,-1},{-1,0},{1,0},{0,1}};
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(grid[i][j])
				continue;
			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++) {
//		for(int j=1; j<=M; j++) {
//			cout << grid[i][j];
//		}
//		cout << '\n';
//	}
	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();
		//cout << x << ' ' << y << '\n';
		for(int k=0; k<4; k++) {
			int xx = x+d[k][0];
			int yy = y+d[k][1];
			if(xx<1 || xx>N || yy<1 || yy>M)
				continue;
			if(vis[xx][yy] || grid[xx][yy])
				continue;
			vis[xx][yy]=1;
			dp[xx][yy] = dp[x][y]+1;
			q.push({xx,yy});
			//cout << x << ' ' << y << ' ' << xx << ' ' << yy << ' ' << dp[xx][yy] << '\n';
		}
	}
	
	int mn = INT_MAX;
	for(int i=1; i<=N; i++) {
		if(dp[i][M]<=0)
			continue;
		mn = min(mn,dp[i][M]);
	}
	
	if(mn==INT_MAX) {
		cout<<-1;
	}
	else {
		cout << mn+1;
	}
}