题目

思路分析

图类的问题一直是我的老大难了，学习时候就没好好学，现在一遇到就懵逼。
这道题最重要的点就是找到网格图的限制以及遍历图计算连通块的数量。所以我们来一个一个分析他们。

网格图的限制

这是个很重要的点，可以优化掉很大的一部分检查过程。
网格图和一般的无向图最大的区别就在于它限制了相连的边数：最多只有四条边。而我们题目的要求是求使得图中1组成的连通块为0或至少为2。也就是说如果题目给出的图本来没有块，或者本来给出的就是包含超过两个连通块的图，那么直接返回0即可。
不满足上边情况时，证明所有的1在一个连通块中，而在网格图中只有四条边，可以考虑最特殊的位置：1组成角落，只要能从角落中分出一个单独的块，就可以满足题目要求，而角落这种特殊位置可能存在的可能性还是很少的：

检查函数

于是接下来比较重要的就是检查连通块是否超过两个的函数了。
可以使用dfs深搜，从每一块1陆地进行dfs，每一次深搜可以找到一个连通块，深搜进行完后判断连通块的数量即可。

    private int[][] g;//矩阵
    private int n, m;//矩阵的高和长
    private boolean[][] visited;//判断结点是否访问过
    private int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    public void dfs(int i, int j){
        visited[i][j] = true;
        for(int k = 0; k < 4; k++){
            int a = i + dx[k];
            int b = j + dy[k];
            if(a >= 0 && a < n && b >= 0 && b < m && !visited[a][b] && g[a][b] == 1)
                dfs(a, b);
        }
    }

    public boolean check(){
        visited = new boolean[n][m];
        int cnt = 0;//连通块的数量

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!visited[i][j] && g[i][j] == 1){
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        return cnt >= 2;
    }

由于网格图只有四个方向，可以使用辅助数组dx, dy便于遍历深搜。

完整代码

有了思路与检查代码，就可以得到完整代码了。

class Solution {

    private int[][] g;//矩阵
    private int n, m;//矩阵的高和长
    private boolean[][] visited;//判断结点是否访问过
    private int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

    public void dfs(int i, int j){
        visited[i][j] = true;
        for(int k = 0; k < 4; k++){
            int a = i + dx[k];
            int b = j + dy[k];
            if(a >= 0 && a < n && b >= 0 && b < m && !visited[a][b] && g[a][b] == 1)
                dfs(a, b);
        }
    }

    public boolean check(){
        visited = new boolean[n][m];
        int cnt = 0;//连通块的数量

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!visited[i][j] && g[i][j] == 1){
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        return cnt >= 2;
    }

    public int minDays(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        g = grid;

        if(check()){
            return 0;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i][j] == 1){
                    g[i][j] = 0;
                    if(check()){
                        return 1;
                    }
                    g[i][j] = 1;
                }
            }
        }
        return 2;
    }
}

总结

自己对图的理解还是很不充分，差的东西真的是太多了，只能一点点的弥补不足了。
如果有写的不对的地方还请指出，感恩相遇~~