算法基础第8天

bfs继续，类似烂橘子，使用扩散法，这里8个方向可以扩散

1091. 二进制矩阵中的最短路径

/**
 1091. 二进制矩阵中的最短路径
 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

 路径途经的所有单元格都的值都是 0 。
 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
 畅通路径的长度 是该路径途经的单元格总数。



 示例 1：


 输入：grid = [[0,1],[1,0]]
 输出：2
 示例 2：


 输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
 输出：4
 示例 3：

 输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
 输出：-1


 提示：

 n == grid.length
 n == grid[i].length
 1 <= n <= 100
 grid[i][j] 为 0 或 1

 * @author zeroheart
 *
 */
public class Question1091 {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if(grid[0][0]!=0){
            return -1;
        }else if( n == 1){
            return 1;
        }

        Queue<int[]> queue = new LinkedList();
        queue.add(new int[]{0, 0});

        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
        int res = 1;


        while (!queue.isEmpty()){
            res++;
            int size = queue.size();
            for(int s = 0; s<size; s++){
                int[] poll = queue.poll();
                int x = poll[0];
                int y = poll[1];

                for(int i = 0; i<8; i++){
                    int nx = dx[i] + x;
                    int ny = dy[i] + y;

                    if(nx>=0 && nx<n && ny>=0 && ny<n){
                        if(grid[nx][ny] == 0){

                            if(nx == n-1 && ny == n-1){
                                return res;
                            }

                            grid[nx][ny] = 1;
                            queue.add(new int[]{nx, ny});
                        }
                    }

                }
            }

        }
        return -1;
    }
}

130. 被围绕的区域

这题理解题目意思比较重要，

和边界上的O直接或者间接相连的，就是没被包围的，先标记A，在还原O，其他的处理为X

/**
 130. 被围绕的区域
 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。


 示例 1：


 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 示例 2：

 输入：board = [["X"]]
 输出：[["X"]]


 提示：

 m == board.length
 n == board[i].length
 1 <= m, n <= 200
 board[i][j] 为 'X' 或 'O'

 * @author zeroheart
 *
 */
public class Question130 {
    public void solve(char[][] board) {
        int n = board.length;
        if (n == 0) {
            return;
        }
        int m = board[0].length;
        // 和边界上的O直接或者间接相连的，就是没被包围的，先标记A，在还原O，其他的处理为X
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[]{i, 0});
                board[i][0] = 'A';
            }
            if (board[i][m - 1] == 'O') {
                queue.offer(new int[]{i, m - 1});
                board[i][m - 1] = 'A';
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (board[0][i] == 'O') {
                queue.offer(new int[]{0, i});
                board[0][i] = 'A';
            }
            if (board[n - 1][i] == 'O') {
                queue.offer(new int[]{n - 1, i});
                board[n - 1][i] = 'A';
            }
        }

        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx < 0 || my < 0 || mx >= n || my >= m || board[mx][my] != 'O') {
                    continue;
                }
                queue.offer(new int[]{mx, my});
                board[mx][my] = 'A';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
}

797. 所有可能的路径

这个和全排列的模版类似，使用回溯法，主要开始我不能看懂他的有向图

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(graph, 0, path, list);
        return list;
    }
    
    public void dfs(int[][] graph, int x, List<Integer> path, List<List<Integer>> list){
        if(x == graph.length - 1){
            list.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < graph[x].length; i++){
            path.add(graph[x][i]);
            dfs(graph, graph[x][i], path, list);
            path.remove(path.size() - 1);
        }
    }

}