Submission

Score: 0

User: kavin8888

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-11-08 14:12:34

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,ans=INT_MAX;
vector<vector<int>> board;
vector<vector<char>> safe;
vector<vector<int>> vis;
bool valid(int x,int y) {
	return 0<=x && x<n && 0<=y && y<m;
}
int dfs(int x,int y) {
	if(y==m-1) return 1;
	if(vis[x][y] != -1) return vis[x][y];
	vis[x][y]=INT_MAX;
	if(valid(x-1,y) && safe[x-1][y] && vis[x-1][y] != 0) {
		int res=dfs(x-1,y);
		if(res != INT_MAX) vis[x][y]=min(vis[x][y],res+1);
	}
	if(valid(x+1,y) && safe[x+1][y] && vis[x+1][y] != 0) {
		int res=dfs(x+1,y);
		if(res != INT_MAX) vis[x][y]=min(vis[x][y],res+1);
	}
	if(valid(x,y-1) && safe[x][y-1] && vis[x][y-1] != 0) {
		int res=dfs(x,y-1);
		if(res != INT_MAX) vis[x][y]=min(vis[x][y],res+1);
	}
	if(valid(x,y+1) && safe[x][y+1] && vis[x][y+1] != 0) {
		int res=dfs(x,y+1);
		if(res != INT_MAX) vis[x][y]=min(vis[x][y],res+1);
	}
	if(vis[x][y] == INT_MAX) vis[x][y]=0;
	return vis[x][y];
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	board.assign(n,vector<int>(m));
	safe.assign(n,vector<char>(m,1));
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			cin>>board[i][j];
		}
	}
	//Mark bomb
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			if(board[i][j]==0) {
				for(int p=max(0,i-1);p<=min(n-1,i+1);p++) {
					for(int q=max(0,j-1);q<=min(m-1,j+1);q++) {
						safe[p][q]=0;
					}
				}
			}
		}
	}
	vis.assign(n,vector<int>(m,-1));
	for(int i=0;i<n;i++) {
		if(safe[i][0]) {
			int res=dfs(i,0);
			if(res>0) ans=min(ans,res);
		}
	}
	cout<<ans<<'\n'; 
	return 0;
}
//5 5
//1 1 1 1 1
//1 1 1 1 0
//1 1 1 1 1
//0 1 1 1 1
//0 1 1 1 1