[算法]DFS-FloodFill

leetcode深度优先搜索-二维平面上的搜索问题Flood Fill

1. 遍历对象（子岛屿问题， 遍历子岛屿）
2. visited访问状态（若是岛屿问题， 只有0、1， 直接用原数据进行标记）
3. 返回
   1. 不返回， 仅标记
   2. 返回boolean
   3. 返回具体值（累加）
4. 主题操作
   1. 自加
   2. 存值
   3. 取大值、取小值
5. 递归出口
   1. 边界
6. 移动方向
   1. 右下[[0, 1], [1, 0]]
   2. 上下左右[[0, 1], [0, -1], [1, 0], [-1, 0]]

      热身

      463. 岛屿的周长（仅迭代， 与dfs无关）

      function islandPerimeter(grid: number[][]): number {
      let m = grid.length, n = grid[0].length;
      let ans = 0;
      for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let top = 0, left = 0;
            if (i > 0) {
                top = grid[i - 1][j];
            }
            if (j > 0) {
                left = grid[i][j - 1];
            }
            let cur = grid[i][j];
            if (cur != top) ++ans;
            if (cur != left) ++ans;
        }
      }
      // 最后一行， 最后一列
      for (let i = 0; i < m; ++i) {
        if (grid[i][n - 1] == 1) ++ans;
      }
      for (let j = 0; j < n; ++j) {
        if (grid[m - 1][j] == 1) ++ans;
      }
      return ans;
      };

      BFS

DFS

初级1

剑指 Offer 13. 机器人的运动范围

以 [0, 0] 为起点， 寻找可行路线
⚠️ 仅需向右、向左即可
dfs

function movingCount(m: number, n: number, k: number): number {
    let visited = Array.from({ length: m }, v => new Array(n).fill(false));
    return dfs(m, n, k, 0, 0, visited);
};

function dfs(m: number, n: number, k: number, i: number, j: number, visited: boolean[][]): number {
    if (i > m - 1 || j > n - 1 || visited[i][j] || getSum(i) + getSum(j) > k) {
        return 0;
    }
    visited[i][j] = true;
    let ans = 1;
    for (let [dx, dy] of [[0, 1], [1, 0]]) {
        let x = i + dx, y = j + dy;
        ans += dfs(m, n, k, x, y, visited);
    }
    return ans;
}

function getSum(num: number): number {
    let ans = 0;
    while (num > 0) {
        ans += (num % 10);
        num = Math.floor(num / 10);
    }
    return ans;
}

bfs

function movingCount(m: number, n: number, k: number): number {
    let visited = Array.from({ length: m }, v => new Array(n).fill(false));
    let queue = [[0, 0]];
    let ans = 1;
    while (queue.length > 0) {
        let [i, j] = queue.shift();
        for (let [dx, dy] of [[0, 1], [1, 0]]) {
            let x = i + dx, y = j + dy;
            if (x > m - 1 || y > n - 1 || visited[x][y] || getSum(x) + getSum(y) > k) {
                continue;
            }
            ++ans;
            visited[x][y] = true;
            queue.push([x, y]);
        }
    }
    return ans;
};

function getSum(num: number): number {
    let ans = 0;
    while (num > 0) {
        ans += (num % 10);
        num = Math.floor(num / 10);
    }
    return ans;
}

200. 岛屿数量

由于只有0、1两种状态，直接修改代替visited标记访问状态
dfs
遍历每个点，搜索整个小岛后并标记为访问， 计数

function numIslands(grid: string[][]): number {
    let m = grid.length, n = grid[0].length;
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                ++ans;
            }
        }
    }
    return ans;
};

function dfs(grid: string[][], i: number, j: number) {
    let m = grid.length, n = grid[0].length;
    if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0';
    for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        let x = i + dx, y = j + dy;
        dfs(grid, x, y);
    }
}

bfs
遍历每个点，（宽度）搜索小岛全部并标记为已访问， 计数

function numIslands(grid: string[][]): number {
    let m = grid.length, n = grid[0].length;
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                bfs(grid, i, j)
                ++ans;
            }
        }
    }
    return ans;
};

function bfs(grid: string[][], r: number, c: number): void {
    let m = grid.length, n = grid[0].length;
    let queue = new Array();
    queue.push([r, c]);
    while (queue.length > 0) {
        let [i, j] = queue.shift();
        for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
            let x = i + dx, y = j + dy;
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                grid[x][y] = '0';
                queue.push([x, y]);
            }
        }
    }
}

695. 岛屿的最大面积

由于只有0、1两种状态，直接修改代替visited标记访问状态
dfs

function maxAreaOfIsland(grid: number[][]): number {
    let m = grid.length, n = grid[0].length;
    let res = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                res = Math.max(dfs(grid, i, j), res);
            }
        }
    }
    return res;
};

function dfs(grid: number[][], i: number, j: number): number {
    let m = grid.length, n = grid[0].length;
    if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] == 0) {
        return 0;
    }
    grid[i][j] = 0;
    let res = 1;
    for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        res += dfs(grid, i + dx, j + dy);
    }
    return res;
}

130. 被围绕的区域

[[“X”,”X”,”X”],[“X”,”O”,”X”],[“X”,”X”,”X”]]
[[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]

/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
    let m = board.length, n = board[0].length;
    if (m < 3 || n < 3) return;
    let visited = Array.from({ length: m }, v => new Array(n).fill(false));
    // 第一行，最后一行， 第一列， 最后一列
    for (let i of [0, m-1]) {
        for (let j = 0; j < n; ++j) {
            if (board[i][j] == 'X') {
                visited[i][j] = true;
            } else {
                dfs(board, i, j, visited, true);
            }
        }
    }
    for (let i = 0; i < m; ++i) {
        for (let j of [0, n - 1]) {
            if (board[i][j] == 'X') {
                visited[i][j] = true;
            } else {
                dfs(board, i, j, visited, true);
            }
        }
    }
    for (let i = 1; i < m - 1; ++i) {
        for (let j = 1; j < n - 1; ++j) {
            !visited[i][j] && dfs(board, i, j, visited);
        }
    }
};

function dfs(board: string[][], i: number, j: number, visited: boolean[][], edge = false): void {
    let m = board.length, n = board[0].length;
    if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visited[i][j]) {
        return;
    }

    visited[i][j] = true;
    if (board[i][j] == 'X') {
        return;
    }
    if (!edge) {
        board[i][j] = 'X';
    }
    for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        let x = i + dx, y = j + dy;
        dfs(board, x, y, visited, edge);
    }
}

进阶

TODO

• 1254. 统计封闭岛屿的数目
• 827. 最大人工岛
• 1568. 使陆地分离的最少天数（贪心）
• 417. 太平洋大西洋水流问题
• 1020. 飞地的数量
• 1034. 边框着色
• 133. 克隆图
• 529. 扫雷游戏

高级

1905. 统计子岛屿

遍历 grid2

function countSubIslands(grid1: number[][], grid2: number[][]): number {
    let m = grid1.length, n = grid1[0].length;
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid2[i][j] == 1 && dfs(grid1, grid2, i, j)) {
                ++ans;
            }
        }
    }
    return ans;
};

function dfs(grid1: number[][], grid2: number[][], i: number, j: number): boolean {
    let m = grid1.length, n = grid1[0].length;
    let ans = true;
    if (grid1[i][j] == 0) {
        ans = false;
    }
    grid2[i][j] = 0;
    for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        let x = i + dx, y = j + dy;
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || grid2[x][y] == 0) {
            continue;
        }
        if (!dfs(grid1, grid2, x, y)) {
            ans = false;
        }
    }
    return ans;
}

LCS 03. 主题空间

⚠️ 边界问题

• Infinity 标记不合法面积
• Infinity = Infinity + number ```typescript function largestArea(grid: string[]): number { let m = grid.length, n = grid[0].length; let visited = Array.from({ length: m }, v => new Array(n).fill(false)); let ans = 0; for (let i = 0; i < m; ++i) {

    for (let j = 0; j < n; ++j) {
        if (grid[i].charAt(j) != '0' && !visited[i][j]) {
            let area = dfs(grid, i, j, visited, grid[i].charAt(j));
            // console.log(i, j, area);
            ans = Math.max(area == Infinity ? 0 : area, ans);
        }
    }
  

  } return ans; };

function dfs(grid: string[], i: number, j: number, visited: boolean[][], target: string): number { let m = grid.length, n = grid[0].length; // 1. 临边岛屿不合法 if (i < 0 || i > m - 1 || j < 0 || j > n - 1) { return Infinity; }

let cur = grid[i].charAt(j);
// 2. 与0相邻岛屿不合法
if (cur == '0') {
    return Infinity;
}
// 递归出口
if (cur != target || visited[i][j]) {
    return 0;
}

let ans = 1;
visited[i][j] = true;
for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
    let x = i + dx, y = j + dy;
    ans += dfs(grid, x, y, visited, target);
}
return ans;

}

<a name="KcTmS"></a>
## （需要）回溯
<a name="ku5dM"></a>
#### [剑指 Offer 12. 矩阵中的路径](https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/)（ [79. 单词搜索](https://leetcode-cn.com/problems/word-search/)）
```typescript
function exist(board: string[][], word: string): boolean {
    let m = board.length, n = board[0].length;
    let visited = Array.from({ length: m }, v => new Array(n).fill(false));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (dfs(board, word, i, j, 0, visited)) {
                return true;
            }
        }
    }
    return false;
};

function dfs(board: string[][], word: string, i: number, j: number, depth: number, visited: boolean[][]): boolean {
    let m = board.length, n = board[0].length;
    if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visited[i][j]) {
        return false;
    }
    if (board[i][j] != word.charAt(depth)) {
        return false;
    }

    if (depth == word.length - 1) {
        return true;
    }

    visited[i][j] = true;
    ++depth;
    let res = false;
    for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        let x = i + dx, y = j + dy;
        res = res || dfs(board, word, x, y, depth, visited);
    }
    visited[i][j] = false;
    return res;
}