AcWing 1076. 迷宫问题 java递归输出
原题链接
简单
作者:
季之秋
,
2021-04-06 21:05:14
,
所有人可见
,
阅读 261
import java.util.*;
public class Main{
static int N = 1010, n;
static int g[][] = new int[N][N];
static Pair pre[][] = new Pair[N][N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++)
g[i][j] = sc.nextInt();
bfs(0, 0);
find(n-1, n-1);
}
static int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
static void bfs(int x, int y){
Queue<Pair> q = new LinkedList();
q.add(new Pair(x, y));
g[x][y] = 1;
while(!q.isEmpty()){
Pair t = q.poll();
for(int i = 0 ; i < 4; i ++){
int a = t.x +dx[i], b = t.y + dy[i];
if(a<0 || b<0 || a>=n || b>=n ) continue;
if(pre[a][b] != null || g[a][b] == 1) continue;
pre[a][b] = t;
q.add(new Pair(a, b));
}
}
}
static void find(int x, int y){ // 终点递归到起点
if(pre[x][y] != null) find(pre[x][y].x, pre[x][y].y);
System.out.println(x+" "+y);
}
static class Pair{
int x, y;
Pair(int a, int b){
x = a;
y = b;
}
}
}