小红书2020笔试题
迷宫游戏
薯队长最近在玩一个迷宫探索类游戏，迷宫是一个
N
∗
N
N*N
N∗N的矩阵形状，其中会有一些障碍物，禁止通过。
这个迷宫还有一个特殊的设计，它的左右边界以及上下边界是连通的，比如在
(
2
,
n
)
(2,n)
(2,n)的位置继续往右走一格
可以到
(
2
,
1
)
(2,1)
(2,1),在
(
1
,
2
)
(1,2)
(1,2)的位置继续往上走一格可以到
(
n
,
2
)
(n,2)
(n,2)。请问薯队长从起点位置S，最少走多少格才能到
迷宫的出口位置E.
输入
第一行正整数N.接下来N行字符串。
‘.'表示可以通过，’#‘表示障碍物，’S'表示起点（有且仅有一个），‘E'表示终点（有且仅有一个）
输出
输出一个整数，表示从S到E最短路径长度，无法到达则输出-1
样例输入
5
.#...
..#S.
.E###
.....
.....
样例输出
4
思路
开始用DFS做，明显超时， 使用BFS, 一遍AC, 样例中可能出现没有出口的情况
java AC代码
import java.util.Scanner;
import java.io.File;
import java.util.Queue;
import java.util.LinkedList;
class Node{
public int x;
public int y;
public int layer;
public Node(int x, int y, int layer) {
this.x = x;
this.y = y;
this.layer = layer;
}
}
public class Main {
public static void main(String[] args) throws Exception{
//File file = new File("in.txt");
//Scanner in = new Scanner(file);
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
char[][] board = new char[n][n];
int startX = -1; int startY = -1;
int endX = -1; int endY = -1;
for (int i = 0; i < n; i++) {
String line = in.nextLine();
for (int j = 0; j < n; j++) {
board[i][j] = line.charAt(j);
if (board[i][j] == 'S') {
startX = i;
startY = j;
} else if (board[i][j] == 'E') {
endX = i;
endY = j;
}
}
}
in.close();
if(startX == -1 && startY == -1) System.out.println("-1");
if(endX == -1 && endY == -1) System.out.println("-1");
Queue<Node> queue = new LinkedList<Node>();
int x = -1; int y = -1;
queue.offer(new Node(startX, startY, 0));
while(!queue.isEmpty()) {
Node node = queue.poll();
//找到最后结果
if (node.x == endX && node.y == endY) {
System.out.println(node.layer);
return;
}
//四个方向
x = node.x + 1; y = node.y;
if(x == n) x = 0;
if(board[x][y] != '#') {queue.offer(new Node(x, y, node.layer + 1)); board[x][y] = '#';}
x = node.x - 1; y = node.y;
if(x == -1) x = n-1;
if(board[x][y] != '#') {queue.offer(new Node(x, y, node.layer + 1)); board[x][y] = '#';}
x = node.x; y = node.y + 1;
if(y == n) y = 0;
if(board[x][y] != '#') {queue.offer(new Node(x, y, node.layer + 1)); board[x][y] = '#';}
x = node.x; y = node.y - 1;
if(y == -1) y = n-1;
if(board[x][y] != '#') {queue.offer(new Node(x, y, node.layer + 1)); board[x][y] = '#';}
}
System.out.println("-1");
}
}
