小红书2020笔试题-迷宫游戏

约定不等于承诺〃 2023-08-17 17:39 129阅读 0赞

#### 小红书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###
    .....
    .....

#### 样例输出 ####

#### 思路 ####

开始用**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");
        }
    }