深度优先遍历

用例通过率: 30%

思路:

通过回溯法,找到起点到终点的 所有 路径。然后,在所有路径中取 最小 的那一个。这种方法仅适用于迷宫 比较小 的时候。如果迷宫很大,大概率 超时了! 事实上,深度优先遍历(DFS)就 不太适用于 求最短路径,它一般适用于找 路径的条数

    public static void main(String[] args) {

        // 以下代码用于输入数据
        Scanner scan = new Scanner(System.in);
        String nmStr = scan.nextLine();
        int n = Integer.valueOf(nmStr.split(" ")[0]);
        int m = Integer.valueOf(nmStr.split(" ")[1]);
        String se = scan.nextLine();
        int xs = Integer.valueOf(se.split(" ")[0]);
        int ys = Integer.valueOf(se.split(" ")[1]);
        int xe = Integer.valueOf(se.split(" ")[2]);
        int ye = Integer.valueOf(se.split(" ")[3]);
        char[][] chrs = new char[n][m];
        for (int i = 0; i < n; i++) {
            String tmpStr = scan.nextLine();
            char[] tmpChar = tmpStr.toCharArray();
            for (int j = 0; j < m; j++) {
                chrs[i][j] = tmpChar[j];
            }
        }

        if (chrs[xe - 1][ye - 1] == '*') {
            System.out.println(-1);
        } else {
            int res = process(chrs, xs - 1, ys - 1, 0, xe - 1, ye - 1);
            System.out.println(res == Integer.MAX_VALUE ? -1 : res);
        }
    }

    public static int process(char[][] chrs, int i, int j, int num, int xe,
                              int ye) {
        if (i == xe && j == ye) {
            return num;
        }
        int n = chrs.length;
        int m = chrs[0].length;
        if (i < 0 || i >= n || j < 0 || j >= m || chrs[i][j] == '*') {
            return Integer.MAX_VALUE;
        }
        chrs[i][j] = '*';
        num++;
        int up = process(chrs, i - 1, j, num, xe, ye);
        int down = process(chrs, i + 1, j, num, xe, ye);
        int left = process(chrs, i, j - 1, num, xe, ye);
        int right = process(chrs, i, j + 1, num, xe, ye);
        // 回溯
        chrs[i][j] = '.';
        num--;
        return Math.min(up, Math.min(down, Math.min(left, right)));
    }

广度优先遍历

用例通过率: 100%

思路:

广度优先遍历,是一种 层次遍历。它从 起点 开始,从上往下从左到右 进行遍历。这种层次遍历,可以确保起点到终点的路径是 最短的最坏情况下,也就是将所有的节点遍历一次,才能找到 终点。但是呢,广度优先遍历不太适用于找 路径的条数,归根结底,还是因为一般的 层次遍历,节点只知道自己 当前所在的层次并不知道自己是由哪一个节点过来的。当然,你可以使用一个 HashMap 来存放每个节点的 上一个节点,但是,对于找 路径数 这种问题来说,并不如 深度优先遍历好

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String[] nm = scan.nextLine().split(" ");
        int n = Integer.valueOf(nm[0].trim());
        int m = Integer.valueOf(nm[1].trim());
        String[] se = scan.nextLine().split(" ");
        int xs = Integer.valueOf(se[0].trim()) - 1;
        int ys = Integer.valueOf(se[1].trim()) - 1;
        int xe = Integer.valueOf(se[2].trim()) - 1;
        int ye = Integer.valueOf(se[3].trim()) - 1;
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            char[] chrs = scan.nextLine().toCharArray();
            for (int j = 0; j < chrs.length; j++) {
                matrix[i][j] = chrs[j];
            }
        }
        if (xs == xe && ys == ye) {
            System.out.println(0);
            return;
        }
        int[][] steps = new int[n][m];
        steps[xs][ys] = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[] tmp = new int[] {xs, ys};
        queue.add(tmp);
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            if (tmp[0] == xe && tmp[1] == ye) {
                break;
            }
            if (tmp[0] - 1 >= 0 && tmp[0] - 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] - 1][tmp[1]] == '.') {
                int[] location = new int[] {tmp[0] - 1, tmp[1]};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0] - 1][tmp[1]] = '*';
            }
            if (tmp[0] + 1 >= 0 && tmp[0] + 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] + 1][tmp[1]] == '.') {
                int[] location = new int[] {tmp[0] + 1, tmp[1]};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0] + 1][tmp[1]] = '*';
            }
            if (tmp[0] >= 0 && tmp[0] < n && tmp[1] - 1 >= 0 && tmp[1] - 1  < m && matrix[tmp[0]][tmp[1] - 1] == '.') {
                int[] location = new int[] {tmp[0], tmp[1] - 1};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0]][tmp[1] - 1] = '*';
            }
            if (tmp[0] >= 0 && tmp[0] < n && tmp[1] + 1 >= 0 && tmp[1] + 1 < m && matrix[tmp[0]][tmp[1] + 1] == '.') {
                int[] location = new int[] {tmp[0], tmp[1] + 1};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0]][tmp[1] + 1] = '*';
            }
        }
        System.out.println(steps[xe][ye] == 0 ? -1 : steps[xe][ye]);
    }

总结:

对于一道问题,到底是使用 深度优先遍历 还是 广度优先遍历,到底是求 路径数 还是 最短路径,不要混。我们应该要发挥这两种 遍历算法 的优势,清楚它们之间的区别。(新手见解)

完整代码如下:

import java.util.*;

public class Main {

    /**********************************************************************************/
    // 深度优先遍历    用例通过率: 30%
    // 思路: 通过回溯法,找到起点到终点的所有路径,然后,在所有路径中取最小的那一个。这种方法仅适用于迷宫比较小的时候。如果迷宫很大,肯定超时了!事实上,深度优先遍历(DFS)就不太适合于,在所有路径中,找到路径最短的,它一般适用于找到底有多少种路径。
    /*
    public static void main(String[] args) {

        // 以下代码用于输入数据
        Scanner scan = new Scanner(System.in);
        String nmStr = scan.nextLine();
        int n = Integer.valueOf(nmStr.split(" ")[0]);
        int m = Integer.valueOf(nmStr.split(" ")[1]);
        String se = scan.nextLine();
        int xs = Integer.valueOf(se.split(" ")[0]);
        int ys = Integer.valueOf(se.split(" ")[1]);
        int xe = Integer.valueOf(se.split(" ")[2]);
        int ye = Integer.valueOf(se.split(" ")[3]);
        char[][] chrs = new char[n][m];
        for (int i = 0; i < n; i++) {
            String tmpStr = scan.nextLine();
            char[] tmpChar = tmpStr.toCharArray();
            for (int j = 0; j < m; j++) {
                chrs[i][j] = tmpChar[j];
            }
        }

        if (chrs[xe - 1][ye - 1] == '*') {
            System.out.println(-1);
        } else {
            int res = process(chrs, xs - 1, ys - 1, 0, xe - 1, ye - 1);
            System.out.println(res == Integer.MAX_VALUE ? -1 : res);
        }
    }

    public static int process(char[][] chrs, int i, int j, int num, int xe,
                              int ye) {
        if (i == xe && j == ye) {
            return num;
        }
        int n = chrs.length;
        int m = chrs[0].length;
        if (i < 0 || i >= n || j < 0 || j >= m || chrs[i][j] == '*') {
            return Integer.MAX_VALUE;
        }
        chrs[i][j] = '*';
        num++;
        int up = process(chrs, i - 1, j, num, xe, ye);
        int down = process(chrs, i + 1, j, num, xe, ye);
        int left = process(chrs, i, j - 1, num, xe, ye);
        int right = process(chrs, i, j + 1, num, xe, ye);
        // 回溯
        chrs[i][j] = '.';
        num--;
        return Math.min(up, Math.min(down, Math.min(left, right)));
    }
    */
    
    /**********************************************************************************/
    // 广度优先遍历    用例通过率: 100%
    // 思路: 广度优先遍历,更像是一种”层次扩散“。它从起点开始,一层一层往下进行遍历(”扩散“),那么,就可以确保起点到终点的路径最短。但是呢,广度优先遍历不太适用于找有多少条路径。因为你是类似”层级“的遍历,你只知道你的上一层是多少,但是,你并不知道你的父节点是谁。
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String[] nm = scan.nextLine().split(" ");
        int n = Integer.valueOf(nm[0].trim());
        int m = Integer.valueOf(nm[1].trim());
        String[] se = scan.nextLine().split(" ");
        int xs = Integer.valueOf(se[0].trim()) - 1;
        int ys = Integer.valueOf(se[1].trim()) - 1;
        int xe = Integer.valueOf(se[2].trim()) - 1;
        int ye = Integer.valueOf(se[3].trim()) - 1;
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            char[] chrs = scan.nextLine().toCharArray();
            for (int j = 0; j < chrs.length; j++) {
                matrix[i][j] = chrs[j];
            }
        }
        if (xs == xe && ys == ye) {
            System.out.println(0);
            return;
        }
        int[][] steps = new int[n][m];
        steps[xs][ys] = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[] tmp = new int[] {xs, ys};
        queue.add(tmp);
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            if (tmp[0] == xe && tmp[1] == ye) {
                break;
            }
            if (tmp[0] - 1 >= 0 && tmp[0] - 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] - 1][tmp[1]] == '.') {
                int[] location = new int[] {tmp[0] - 1, tmp[1]};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0] - 1][tmp[1]] = '*';
            }
            if (tmp[0] + 1 >= 0 && tmp[0] + 1 < n && tmp[1] >= 0 && tmp[1] < m && matrix[tmp[0] + 1][tmp[1]] == '.') {
                int[] location = new int[] {tmp[0] + 1, tmp[1]};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0] + 1][tmp[1]] = '*';
            }
            if (tmp[0] >= 0 && tmp[0] < n && tmp[1] - 1 >= 0 && tmp[1] - 1  < m && matrix[tmp[0]][tmp[1] - 1] == '.') {
                int[] location = new int[] {tmp[0], tmp[1] - 1};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0]][tmp[1] - 1] = '*';
            }
            if (tmp[0] >= 0 && tmp[0] < n && tmp[1] + 1 >= 0 && tmp[1] + 1 < m && matrix[tmp[0]][tmp[1] + 1] == '.') {
                int[] location = new int[] {tmp[0], tmp[1] + 1};
                queue.add(location);
                steps[location[0]][location[1]] = steps[tmp[0]][tmp[1]] + 1;
                matrix[tmp[0]][tmp[1] + 1] = '*';
            }
        }
        System.out.println(steps[xe][ye] == 0 ? -1 : steps[xe][ye]);
    }
}