Submission

Score: 0

User: VggT

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

Language: cpp

Time: 0.245 second

Submitted On: 2026-03-12 21:11:55

#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;
		}
	}
}

void path(vector<vector<int>> &grid,int i, int j, int &minimum,int count,vector<vector<bool>> &visited)
{
	if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0 || visited[i][j]) return;
	if(j == grid[0].size()-1)
	{
//		cout << count << '\n';
		minimum = min(minimum,count);
		return;
	}
	
	visited[i][j] = true;
	
	path(grid,i,j+1,minimum,count+1,visited);
	path(grid,i+1,j,minimum,count+1,visited);
	path(grid,i-1,j,minimum,count+1,visited);
	
	
	
}

int main()
{
	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;
	
	int minimum = INT_MAX;
	
	for(int i = 0; i < grid.size(); i+=1)
	{
		vector<vector<bool>> visited(n,vector<bool>(m,false));
		path(grid,i,0,minimum,1,visited);
	}
	
	
	
	if(minimum == INT_MAX) cout << -1;
	else cout << minimum;

//	cout << '\n';
//	
//	for(auto a : grid)
//	{
//		for(auto b : a)
//		{
//			cout << b << ' ';
//		}
//		cout << '\n';
//	}
	
	
	
	
	
	
	return 0;
}