Submission

Score: 0

User: nemuchannnUwU

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

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-06 18:59:12

#include<bits/stdc++.h>
using namespace std;
int dx[]={1,-1,0,0,-1,1,1,-1};
int dy[]={0,0,1,-1,1,1,-1,-1};

int _canx[]={0,0,1,-1};
int _cany[]={-1,1,0,0};
bool chk(int x,int y,int n,int m){
	return (x>=0&&x<n&&y>=0&&y<m);
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	int n,m; cin >> n >> m;
	int mn=INT_MAX;
	vector<vector<int>> grid(n,vector<int>(m));
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			cin >> grid[i][j];
		}
	}
	vector<vector<int>> block=grid;
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			if (grid[i][j]==0){
				for (int k=0;k<8;k++){
					int nx=i+dx[k];
					int ny=j+dy[k];
					if (chk(nx,ny,n,m)){
						block[nx][ny]=0;
					}
				}
			}
		}
	}
	for (int i=0;i<n;i++){
		vector<vector<bool>> visited(n,vector<bool> (m,false));
		visited[i][0]=true;
		queue<tuple<int,int,int>> q;
		q.push({i,0,0});
		while(!q.empty()){
			auto [x,y,dist]=q.front();
			q.pop();
			
			if (y==m-1){
				mn=min(dist,mn);
				break;
			}
			for (int j=0;j<4;j++){
				int nx=x+dx[j];
				int ny=y+dy[j];
				if (chk(nx,ny,n,m)&&!visited[nx][ny]&&block[nx][ny]!=0){
					dist+=1;
					visited[nx][ny]=true;
					q.push({nx,ny,dist});
				}
			}
		}
	}

	
	if (mn==INT_MAX) cout << "-1";
	else cout << mn;
}