AcWing 844. 走迷宫
原题链接
简单
作者:
STU756
,
2021-02-07 02:44:52
,
所有人可见
,
阅读 457
import java.util.*;
import java.io.*;
public class Main{
static class Pair {
int x;
int y;
public Pair(int x,int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws Exception{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String[] nums = br.readLine().split(" ");
int n = Integer.parseInt(nums[0]), m = Integer.parseInt(nums[1]);
int[][] a = new int[110][110];
boolean[][] visited = new boolean[110][110];
for(int i = 1; i <= n; i++) {
String[] numsStrs = br.readLine().split(" ");
for(int j= 1; j <= m; j++) {
a[i][j] = Integer.parseInt(numsStrs[j-1]);
}
}
if(a[1][1] == 1 || a[n][m] == 1) throw new IllegalArgumentException("input error");
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(1, 1));
int res = 0;
visited[1][1] = true;
while(!q.isEmpty()) {
int size = q.size();
while(size-- > 0) {
Pair p = q.poll();
if(p.x == n && p.y == m) {
System.out.println(res);
return;
}
for(int i = 0; i < 4; i++) {
int x = p.x + dx[i];
int y = p.y + dy[i];
if(x >= 1 && x <= n && y >= 1 && y <= m && !visited[x][y] && a[x][y]!=1) {
visited[x][y] = true;
if(x == n && y == m) {
System.out.println(res + 1);
return;
}
q.offer(new Pair(x, y));
}
}
}
++res;
}
}
}