【纵火犯的春天】纵火犯是如何解题leetcode的?

D4

大家好，这种理解思路是我在这道题目的评论区偶然看到的，觉得很有意思，所以打算写成题解的方式加深一下对类似题目的理解。

200.岛屿数量（原题链接）

这个题目可以考虑DFS（深度优先）解决，但是暴力好像也能做，但是非常非常繁琐，远没有递归来的简洁高效，正好这个题目也可以练习熟悉一下递归。

解题思路：

想想我们是一位纵火犯，我们的目的是烧光所有的陆地，可是现在有个问题，陆地并不全是连续的，所以就产生了岛屿，我们想要烧光每一块陆地，就必须到达一块陆地相邻的所有陆地，称之为一个“岛屿”。

海的位置是'0'，未被访问的陆地的位置是'1'，那我们就想，我烧完这块陆地，我就得标记一下，这里用'2'表示，下次就不用来了。之后我们要去上下左右四个方向看看周围还有没去过的陆地吗，如果有，烧掉并做标记。一段时间过后，我们发现没路了，前面是海，后面是已做好标记的烧光的陆地，那我们就要考虑停下了，这就是烧光的一整个岛屿。再去找其他还是'1'的地方（在这里我们可以for循环遍历所有地点找到），为节省时间，我们不会再踏足已烧光的岛屿，所以需要在纵火前判断一下这里是不是'1'，重复以上过程。

那dfs的结束条件是什么？

• 周围都是烧光的陆地了
• 遇到海了

细分就是数组下标越界：< 0或者>= length，因为是从0开始计数，所以达到length就已经是海了。

这个题目体现的深度优先遍历思想在于，这里比如dfs(grid, i - 1, j);//向上走，我要向上走，我就一直向上走，直到不能继续走下去。也就是优先探索某个方向到底，然后回溯

class Solution {
    public int numIslands(char[][] grid) {
        int ans = 0; //记数器
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == '1'){//如果当前是未涉足的陆地
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2'; //将此地标记为已访问
        dfs(grid, i - 1, j);//向上走
        dfs(grid, i + 1, j);//向下走
        dfs(grid, i, j - 1);//向左走
        dfs(grid, i, j + 1);//向右走
    }
}