Submission

Score: 100

User: VggT

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

Language: cpp

Time: 0.136 second

Submitted On: 2026-03-12 21:33:12

#include <bits/stdc++.h>
using namespace std;
void changeBoard(vector<vector<int>> &grid, int posi, int posj)
{
	for(int i = posi-1; i <= posi+1; i+=1)
	{
		for(int j = posj-1; j <= posj+1; j+=1)
		{
			if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) continue;
			grid[i][j] = 0;
		}
	}
}

int bfs(vector<vector<int>> &grid)
{
	queue<vector<int>> q;
	for(int i = 0; i < grid.size(); i+=1)
	{
		q.push({i,0,1});
	}
	
	int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
	
	
	while(!q.empty())
	{
		int i = q.front()[0];
		int j = q.front()[1];
		int count = q.front()[2];
		q.pop();
		if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) continue;
		if(j == grid[0].size()-1) return count;
		grid[i][j] = 0;
		for(auto a : dirs)
		{
			q.push({i+a[0],j+a[1],count+1});
		}
	}
	return -1;
}



int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	vector<vector<int>> grid(n,vector<int>(m));
	for(auto &a : grid) for(auto &b : a) cin >> b;
	
	vector<vector<int>> gridcopy = grid;
	
	for(int i = 0; i < grid.size(); i+=1)
	{
		for(int j = 0; j < grid[0].size(); j+=1)
		{
			if(grid[i][j] == 0)
			{
				changeBoard(gridcopy,i,j);
			}
		}
	}
	
	
	grid = gridcopy;
	
	
	
	cout << bfs(grid);
	
	
	
	


	
	
	
	
	
	return 0;
}