LeetCode 1568. 使陆地分离的最少天数（DFS）

示例 1：
输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
输出：2
解释：至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。

示例 2：
输入：grid = [[1,1]]
输出：2
解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。

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

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

示例 5：
输入：grid = [[1,1,0,1,1],
             [1,1,1,1,1],
             [1,1,0,1,1],
             [1,1,1,1,1]]
输出：2
 
提示：
1 <= grid.length, grid[i].length <= 30
grid[i][j] 为 0 或 1

class Solution {
	vector<vector<int>> dir = {{-1,0},{0,1},{0,-1},{1,0}};
	int m, n;
public:
    int minDays(vector<vector<int>>& grid) {
    	m = grid.size(), n = grid[0].size();
    	int island = computeIsland(grid);
    	if(island == 0 || island > 1)
    		return 0;
    	for(int i = 0, j; i < m; ++i)
    	{
    		for(j = 0; j < n; ++j)
    		{
    			if(grid[i][j] == 0)
    				continue;
    			grid[i][j] = 0;//将这个土地变成水
    			island = computeIsland(grid);
    			if(island == 0 || island > 1)
    				return 1;
                grid[i][j] = 1;//回溯
    		}
    	}
    	return 2;
    }

    int computeIsland(vector<vector<int>>& grid)
    {
        int island = 0;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for(int i = 0, j; i < m; ++i)
    	{
    		for(j = 0; j < n; ++j)
    		{
    			if(grid[i][j] == 0 || vis[i][j])
    				continue;
    			island++;
                vis[i][j] = true;
    			dfs(grid, i, j, vis);
    		}
    	}
        return island;
    }
    void dfs(vector<vector<int>>&grid, int i, int j, vector<vector<bool>>& vis)
    {
    	int x, y, k;
    	for(k = 0; k < 4; k++) 
    	{
    		x = i + dir[k][0];
    		y = j + dir[k][1];
    		if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y])
    		{
    			vis[x][y] = true;
    			dfs(grid, x, y, vis);
    		}
    	}
    }
};