题意：给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将任何单个陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
思路：这题咋一看是一个tarjan 找图的割点的问题，以我现在这个水平，肯定是敲不出来的。瞄了一眼官方题解，发现这题的答案最大是2。最差的情况就是上下左右四个点都是1，这时候只需要把对角线砍了，图就不连通了。
所以就很好做了，如果原始图就不是一个强连通图，那么输出0。对于答案是1的情况，遍历所有1的点，如果去掉这个点之后不是一个强连通图，那么答案是1。否则答案是2。并查集就能做。
所以以后看到题目还是多想想解法吧~~~
C++代码：
class Solution {
public:
int father[1010];
int getfa(int u){
if(father[u] == u) return u;
father[u] = getfa(father[u]);
return father[u];
}
void merge(int u, int v){
int fu = getfa(u);
int fv = getfa(v);
if(fu != fv) father[fv] = fu;
}
bool judge(vector<vector<int>> grid){
int n = grid.size();
int m = grid[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int id = i * m + j;
father[id] = id;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int id = i * m + j;
if(grid[i][j] == 1){
if(i > 0 && grid[i-1][j] == 1){
int jd = (i - 1) * m + j;
merge(id, jd);
}
if(j > 0 && grid[i][j-1] == 1){
int jd = i * m + j - 1;
merge(id, jd);
}
if(i < n - 1 && grid[i+1][j] == 1){
int jd = (i + 1) * m + j;
merge(id, jd);
}
if(j < m - 1 && grid[i][j+1] == 1){
int jd = i * m + j + 1;
merge(id, jd);
}
}
}
}
int res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int id = i * m + j;
if(grid[i][j] == 1 && getfa(id) == id) {
res ++;
}
}
}
if(res > 1 || res == 0) return true;
return false;
}
int minDays(vector<vector<int>>& grid) {
int n = grid.size();
if(n == 0) return 0;
if(judge(grid)) return 0;
int m = grid[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
grid[i][j] = 0;
if(judge(grid)) return 1;
grid[i][j] = 1;
}
}
}
return 2;
}
};
网友评论