矩阵路径

1.枚举不同路径

在二维网格 grid 上，有 4 种类型的方格： leetcode 980 剑指offer12 剑指offer13 1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

DFS模版

1. 减枝条件： 数组越界 ，遇到障碍
2. 方向数组

3. 做选择 撤销选择 ```java public int uniquePathsIII(int[][] grid) { int m = grid.length; int n = grid[0].length; this.grid = grid;

   dfs(m,n,入口坐标); return res; }

int[] dx = {0,0,1,-1}; int[] dy = {1,-1,0,0}; int[][] grid; int res = 0; public void dfs(int m, int n, int x,int y){ if(x == m || x == -1 || y == n || y == -1 || grid[x][y] == -1) return;

if(grid[x][y] == 2  ){
    if(是否所有方格都被走过)){
        res++;
    }
    return;
} 
grid[x][y] = -1;
for(int i = 0 ; i < 4; i++){
    dfs(m, n, x + dx[i],y + dy[i]);
}
grid[x][y] = 0;

}

<a name="uCtza"></a>
### 2.网格中的最短路径

---

> 给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
> 如果您 **最多 可以消除 k 个障碍物**，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1
> [**leetcode 1293**](https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination)

<a name="LCXxi"></a>
#### BFS模版 三维visited数组标记
```java
private int bfs(int[][] grid, int k){
    int m = grid.length;
    int n = grid[0].length;

    Queue<Node> queue = new LinkedList<Node>();
    int[][][] visited = new int[m][n][k+1];
    int step = 0;

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

    queue.offer(new Node(0,0,0));
    visited[0][0][0] = 1;

    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i = 0;i < size;i++){
            Node pos = queue.poll();
            if(pos.x == m-1 && pos.y == n-1) return step;

            for(int j = 0;j < 4;j++){
                int xNew = pos.x + dx[j];
                int yNew = pos.y + dy[j];
                // 越界
                if (xNew < 0 || xNew >= m || yNew < 0 || yNew >= n) {
                    continue;
                }
                // 消除次数满
                if(grid[xNew][yNew] == 1 && pos.z == k){
                    continue;
                }
                int zNew = grid[xNew][yNew] == 1 ? pos.z + 1 : pos.z;
                // 标记该节点被访问过
                if(visited[xNew][yNew][zNew] == 1) continue;
                else{
                    visited[xNew][yNew][zNew] = 1;
                }
                queue.offer(new Node(xNew,yNew,zNew));
            }
        }
        step++;
    }
    return -1;
}

class Node{
    int x;
    int y;
    int z;

    public Node(int x,int y,int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

3.被围绕的区域

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

BFS/DFS

并查集 虚拟节点

1. 二维坐标(x,y)可以转换成x * n + y这个数（m是棋盘的行数，n是棋盘的列数）。
2. 索引[0.. mn-1]都是棋盘内坐标的一维映射，那就让这个虚拟的dummy节点占据索引mn好了。

3. 所有不和 dummy 连通的 O，都要被替换

   void solve(char[][] board) {
    if (board.length == 0) return;
   
    int m = board.length;
    int n = board[0].length;
    // 给 dummy 留一个额外位置
    UF uf = new UF(m * n + 1);
    int dummy = m * n;
    // 将首列和末列的 O 与 dummy 连通
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O')
            uf.union(i * n, dummy);
        if (board[i][n - 1] == 'O')
            uf.union(i * n + n - 1, dummy);
    }
    // 将首行和末行的 O 与 dummy 连通
    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O')
            uf.union(j, dummy);
        if (board[m - 1][j] == 'O')
            uf.union(n * (m - 1) + j, dummy);
    }
    // 方向数组 d 是上下左右搜索的常用手法
    int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (board[i][j] == 'O')
                // 将此 O 与上下左右的 O 连通
                for (int k = 0; k < 4; k++) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    if (board[x][y] == 'O')
                        uf.union(x * n + y, i * n + j);
                }
    // 所有不和 dummy 连通的 O，都要被替换
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (!uf.connected(dummy, i * n + j))
                board[i][j] = 'X';
   }