Submission

Score: 100

User: navysrimuang

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

Language: cpp

Time: 0.098 second

Submitted On: 2026-03-12 23:23:57

#include<bits/stdc++.h>
using namespace std;

bool grid[1005][1005];

int dy[] = {-1,-1,-1,0,1,1,1,0};
int dx[] = {-1,0,1,1,1,0,-1,-1};

int kx[] = {0,1,0,-1};
int ky[] = {1,0,-1,0};

int main(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			int a;
			cin >> a;
			if(!a){
				grid[i][j] = 1;
				for(int k = 0;k<8;k++){
					grid[i+dy[k]][j+dx[k]] = 1;	
				}
			}
		}
	}
	//multi-source bfs???
	queue<pair<int,int>> q;
	vector<vector<int>> dist(n+5,vector<int>(m+5,-1));	
	for(int i = 1;i<=n;i++){
		if(!grid[i][1]){
			dist[i][1] = 1;
			q.push({i,1});
		}
	}

	while(q.size()){
		auto [x,y] = q.front();
		q.pop();

		for(int i = 0;i<4;i++){
			int xx = x+kx[i];
			int yy = y+ky[i];
			if(xx < 1 || yy < 1 || xx > n || yy > m || grid[xx][yy] || dist[xx][yy] != -1) continue;
			dist[xx][yy] = 1 + dist[x][y];
			if(yy == m){
				cout << dist[xx][yy] << "\n";
				return 0;
			}
			q.push({xx,yy});
		}
	}
	
	cout << -1 << "\n";
	return 0;
}