王子与公主

绝地灬酷狼 2022-12-08 12:53 118阅读 0赞

# 王子与公主 #

## 1、题目要求 ##

> 题目描述(From JD)

![2020-09-17\_203823][2020-09-17_203823]

> 示例

![2020-09-17\_203833][2020-09-17_203833]

## 2、代码思路 ##

迷宫问题

额，怎么说呢，很像[之前老韩讲的迷宫问题][Link 1]，其本质就是递归深度搜索、回溯的过程，因为递归到最深层，我才能知道这条路到底走不走得通，走得通我就 `return true;` 进行回溯，走不通我就 `return false;` 进行回溯

--------------------

我们规定函数 `boolean findWay(char[][] map, int row, int col) {` 用于寻找路径：

1.  如果 `map[row][col] == 'E'` 表示找到公主，我们 `return true` 进行回溯
2.  如果 `map[row][col] == '.'` 表示此路可走，那我们就尝试着走这个格子，然后将其设置为 `','`，表示此路已走过(防止搜寻路径的时候重复走，造成死递归)，然后我们尝试着向上、向下、向左、向右搜寻路径
3.  否则，剩下的情况就是 `map[row][col] == ','`(此路已经走过) 或者 `map[row][col] == '#'`(此路不通)，这两种情况都不应该再走此单元格，`return false` 进行回溯即可

--------------------

关于路径策略

1.  我这里选择了先向上、再向下、再向右、再向左的策略，路径策略可随意选择，因为我们在搜索路径的时候，也不知道哪条路径才是最优路径
2.  如果当前单元格未走过，即 `if (map[row][col] == '.') {`，那么我们就尝试着走该单元格，然后将其设置为 `map[row][col] = ',';`，表示该单元格已经走过，告诉后面的递归哥们：我这条路已经走过了，你不要再走了，不信的话，你就尝试下死递归咯
3.  那么走了当前单元格，我们尝试着向上走，前提是向上走不越界，并且向上走能走通，即判断条件为 `(row + 1) < map.length && findWay(map, row + 1, col)`
4.  向下、向右、向左的道理相同，即不越界，并且能走通，就走该条路，最后如果向上、向下、向右、向左都不能走通，那么表示该单元格无法走通，将其设置为 `'#'`，表示走不通啦

## 3、代码实现 ##

代码

/**
     * @ClassName PrincePrincessDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/17 19:56
     * @Version 1.0
     */
    public class PrincePrincessDemo {
        
    
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            String line = scanner.nextLine();
            int count = Integer.parseInt(line); // 测试组数
            List<String> result = new ArrayList<>(); // 每组测试的结果
            for (int i = 0; i < count; i++) {
        
                line = scanner.nextLine();
                int n = Integer.parseInt(line.split(" ")[0]); // 地图行数
                int m = Integer.parseInt(line.split(" ")[1]); // 地图列数
                char[][] map = new char[n][];
                for (int row = 0; row < n; row++) {
        
                    line = scanner.nextLine();
                    map[row] = line.toCharArray();
                }
                int[] start = findStart(map);
                boolean isSuccess = findWay(map, start[0], start[1]); // 寻找公主
                if (isSuccess == true) {
        
                    result.add("YES");
                } else {
        
                    result.add("NO");
                }
            }
            for (String res : result) {
        
                System.out.println(res);
            }
        }
    
        /**
         * 找到王子的位置
         *
         * @param map 地图二维数组
         * @return 王子所在的行列坐标
         */
        public static int[] findStart(char[][] map) {
        
            int[] result = new int[2];
            for (int row = 0; row < map.length; row++) {
        
                for (int col = 0; col < map[0].length; col++) {
        
                    // 找到王子所在位置，并将其设置为 '.'，表示此路可走通
                    if (map[row][col] == 'S') {
        
                        map[row][col] = '.';
                        result[0] = row;
                        result[1] = col;
                    }
                }
            }
            return result;
        }
    
        /**
         * 搜索迷宫里路径
         *
         * @param map 地图二维数组
         * @param row 当前出发点所在的行
         * @param col 当前出发点所在的列
         * @return 该条路是否能走通
         */
        public static boolean findWay(char[][] map, int row, int col) {
        
            // 找到公主返回 true
            if (map[row][col] == 'E') {
        
                return true;
            }
    
            // 否则该单元格能走，尝试走这条单元格
            if (map[row][col] == '.') {
        
                // 将其设置为 ','，表示此路已走过
                map[row][col] = ',';
                if ((row + 1) < map.length && findWay(map, row + 1, col)) {
         // 尝试着向上走
                    return true;
                } else if ((row - 1) >= 0 && findWay(map, row - 1, col)) {
         // 尝试着向下走
                    return true;
                } else if ((col + 1) < map[0].length && findWay(map, row, col + 1)) {
         // 尝试着向右走
                    return true;
                } else if ((col - 1) >= 0 && findWay(map, row, col - 1)) {
         // 尝试着向左走
                    return true;
                } else {
        
                    // 否则，向上、向下、向右、向左都不能走通，将其设置为 '#'
                    map[row][col] = '#';
                    // return false，表示此路不通
                    return false;
                }
            } else {
        
                // 否则，map[row][col] = ',' 或 map[row][col] == '#'
                // 这两种情况都不应该再走此单元格，return false 进行回溯即可
                return false;
            }
        }
    
    }

[2020-09-17_203823]: /images/20221123/71a0d2ec90224dd5abb74b685c98eb99.png
[2020-09-17_203833]: /images/20221123/21a92b81830f43e0aef60fe96e837492.png
[Link 1]: https://blog.csdn.net/oneby1314/article/details/107844718