深度优先搜索

矩阵背景

面试题13. 机器人的运动范围

问题描述：

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。

案例展示：

例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。

问题：

请问该机器人能够到达多少个格子？

class Solution {
    private int digSum(int x) {
        return x / 10 + x % 10;
    }

    private boolean checkPosition(int i, int j, int k, boolean[][] visited) {
        int m = visited.length;
        int n = visited[0].length;
        // 标准化检查: 检查下标合法性和访问标志
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
            return false;
        }
        // 定制化检查: 根据题目要求确定, 行坐标和列坐标数位之和不大于k
        return digSum(i) + digSum(j) <= k;
    }

    // dfs核心逻辑
    private int movingCountDFS(int i, int j, int k, boolean[][] visited) {
        // 当前遍历位置[i,j]的合法性检查
        if (!checkPosition(i, j, k, visited)) {
            return 0;
        }

        // 位置合法
        int result = 0;
        // 设置访问标记
        visited[i][j] = true;
        // 每次允许的运动策略: 上、下、左、右
        result += movingCountDFS(i, j - 1, k, visited);
        result += movingCountDFS(i, j + 1, k, visited);
        result += movingCountDFS(i - 1, j, k, visited);
        result += movingCountDFS(i + 1, j, k, visited);
        // 当前位置允许访问, 结果值 + 1
        return ++result;
    }

    // 入口函数, 从[0,0]位置开始即可, 可以不需要嵌套两层for循环从任意位置开始扫描, 这个取决于具体问题, 这里采用通用模板
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];

        int result  = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                result += movingCountDFS(i, j, k, visited)
            }
        }
        return result;
    }
}

图背景

207. 课程表

问题描述：

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

案例展示：

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

问题：

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

BFS

思路：

• 邻接表 + 入度表 + BFS队列
• 依次 “删除” 入度为 0 的节点

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjs = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjs.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            indegrees[prerequisite[0]]++;
            adjs.get(prerequisite[1]).add(prerequisite[0]);
        }

        Queue<Integer> queue = new LinkedList<>();
        // 初始化队列
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0) {
                numCourses--;
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int adjNode : adjs.get(node)) {
                if (--indegrees[adjNode] == 0) {
                    numCourses--;
                    queue.offer(adjNode);
                }
            }
        }
        return numCourses == 0;
    }
}

DFS

思路：

• 三种遍历状态
  • 0：未遍历
  • 1：正在遍历
  • -1：已遍历

210. 课程表

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

    }
}