@蓝桥杯 全球变暖 简单写法 超详细
题目链接：全球变暖
思路:
**这道的大致写法就是用dfs将各个岛屿先编号（vis值）作为t，
编完号之后将上下左右有' . '这个字符的' # '的vis值改为0，
之后遍历整个字符数组，查找还剩几个vis数不为0，作为 h(当然不能重复计算）
再用t-h+1(为什么要加1？因为有些vis值一开始就是0）
那么下面就是具体代码，具体请看注释**
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e3+5;
int n
,t
,h
,res
[N
],vis
[N
][N
];
char a
[N
][N
];
int dx
[4]={0,1,0,-1};
int dy
[4]={1,0,-1,0};
bool Check(int x
,int y
){
if(x
>n
||x
<=0||y
>n
||y
<=0)
return false;
return true;
}
void dfs(int x
,int y
,int t
){
if(a
[x
][y
]!='#'||vis
[x
][y
]!=0)
return ;
if(!Check(x
,y
))
return ;
vis
[x
][y
]=t
;
for(int i
=0;i
<=3;i
++)
dfs(x
+dx
[i
],y
+dy
[i
],t
);
}
int main(){
cin
>>n
;
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
cin
>>a
[i
][j
];
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
if(a
[i
][j
]=='#'&&!vis
[i
][j
])
dfs(i
,j
,++t
);
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
if(a
[i
][j
]=='#'){
for(int k
=0;k
<=3;k
++)
if(a
[i
+dx
[k
]][j
+dy
[k
]]=='.'){
vis
[i
][j
]=0;
break;
}
}
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
if(a
[i
][j
]=='#')
if(!res
[vis
[i
][j
]]){
h
++;
res
[vis
[i
][j
]]=1;
}
cout
<<t
-h
+1;
return 0;
}
