Submission

Score: 100

User: kavin8888

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

Language: cpp

Time: 0.092 second

Submitted On: 2025-12-11 18:04:33

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> board;
vector<vector<int>> dist;
queue<pair<int,int>> q;
pair<int,int> DI[4]={{-1,0},{1,0},{0,-1},{0,1}};
bool valid(int x,int y) {
	return 0<=x && x<n && 0<=y && y<m;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	board.assign(n,vector<int>(m));
	dist.assign(n,vector<int>(m,INT_MAX));
	for(int i=0;i<n;++i) {
		for(int j=0;j<m;++j) {
			cin>>board[i][j];
			if(board[i][j]==0) {
				q.push({i,j});
			}
		}
	}
	while(!q.empty()) {
		auto [x,y] =q.front(); q.pop();
		for(int i=x-1;i<=x+1;++i) {
			for(int j=y-1;j<=y+1;++j) {
				if(!valid(i,j)) continue;
				board[i][j]=0;
			}
		}
	}
	for(int i=0;i<n;++i) {
		if(board[i][0]==1) {
			q.push({i,0});
			dist[i][0]=1;
		}
	}
	while(!q.empty()) {
		auto [x,y] =q.front(); q.pop();
		for(int i=0;i<4;++i) {
			auto &[xi,yi] = DI[i];
			if(y==m-1) {
				cout<<dist[x][y]<<'\n';
				return 0;
			}
			if(valid(x+xi,y+yi) && board[x+xi][y+yi]==1 && dist[x][y]+1<dist[x+xi][y+yi]) {
				q.push({x+xi,y+yi});
				dist[x+xi][y+yi]=dist[x][y]+1;
			}
		}
	}
	cout<<"-1\n";
	return 0;
}