信息学奥赛一本通T1255-迷宫问题

解题思路:使用宽度优先搜索解题

注意事项:题目测试数据不好,一定要使用{ { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };这个顺序不然会报答案错误.
参考代码:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int arrays[][] = new int[5][5];
static boolean bu[][] = new boolean[5][5];
static int direction[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
arrays[i][j] = scanner.nextInt();
}
}
sout(bfs());
}
static Connect bfs() {
Queue<Connect> queue = new LinkedList<>();
Connect temp = new Connect(0, 0, null);
queue.add(temp);
while (!queue.isEmpty()) {
temp = queue.poll();
int x1 = temp.x;
int y1 = temp.y;
if (x1 == 4 && y1 == 4) {
break;
}
for (int i = 0; i < 4; i++) {
int x = x1 + direction[i][0];
int y = y1 + direction[i][1];
if (x < 5 && x >= 0 && y < 5 && y >= 0 && arrays[x][y] != 1 && !bu[x][y]) {
Connect temp1 = new Connect(x, y, temp);
queue.add(temp1);
bu[x][y] = true;
}
}
}
return temp;
}
static void sout(Connect temp) {
Connect tempConnect = temp.Rootnode;
if (tempConnect == null) {
System.out.println("(0, 0)");
return;
}
sout(tempConnect);
System.out.println("(" + temp.x + ", " + temp.y + ")");
}
}
class Connect {
int x;
int y;
Connect Rootnode;
public Connect(int x, int y, Connect rootnode) {
super();
this.x = x;
this.y = y;
Rootnode = rootnode;
}
}