题目描述
小蓝得到了一副大小为 M×N 的格子地图,可以将其视作一个只包含字符 0(代表海水)和 1(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。
在岛屿 A 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列:(x0,y0),(x1,y1),…,(xk−1,yk−1),其中 (x(i+1)%k,y(i+1)%k) 是由 (xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1),此时这 k 个格子就构成了一个 “环”。
如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部,此时我们将岛屿 B 视作是岛屿 A 的子岛屿。
若 B 是 A 的子岛屿,C 又是 B 的子岛屿,那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿?
在进行统计时不需要统计子岛屿的数目。
dfs暴力搜索
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
char a[60][60];
int n,m,ans;
void dfs1(int w,int h)
{
a[w][h]='#';
if(w+1<=m&&a[w+1][h]=='1')
{
dfs1(w+1,h);
}
if(w-1>0&&a[w-1][h]=='1')
{
dfs1(w-1,h);
}
if(h+1<=n&&a[w][h+1]=='1')
{
dfs1(w,h+1);
}
if(h-1>0&&a[w][h-1]=='1')
{
dfs1(w,h-1);
}
}
void dfs(int w,int h)
{
if(a[w+1][h+1]=='1'){
ans++;
dfs1(w+1,h+1);
}
if(a[w][h+1]=='1'){
ans++;
dfs1(w,h+1);
}
if(a[w][h-1]=='1'){
ans++;
dfs1(w,h-1);
}
if(a[w+1][h]=='1'){
ans++;
dfs1(w+1,h);
}
if(a[w-1][h+1]=='1'){
ans++;
dfs1(w-1,h+1);
}
if(a[w-1][h]=='1'){
ans++;
dfs1(w-1,h);
}
if(a[w-1][h-1]=='1'){
ans++;
dfs1(w-1,h-1);
}
if(a[w+1][h-1]=='1'){
ans++;
dfs1(w+1,h-1);
}
a[w][h]='#';
if(h+1<=n+1&&w+1<=m+1&&a[w+1][h+1]=='0')
{
dfs(w+1,h+1);
}
if(w+1<=m+1&&a[w+1][h]=='0')
{
dfs(w+1,h);
}
if(w-1>=0&&a[w-1][h]=='0')
{
dfs(w-1,h);
}
if(h+1<=n+1&&a[w][h+1]=='0')
{
dfs(w,h+1);
}
if(h-1>=0&&a[w][h-1]=='0')
{
dfs(w,h-1);
}
if(h-1>=0&&w-1>=0&&a[w-1][h-1]=='0')
{
dfs(w-1,h-1);
}
if(h-1>=0&&w+1<=m+1&&a[w+1][h-1]=='0')
{
dfs(w+1,h-1);
}
if(h+1<=n+1&&w-1>=0&&a[w-1][h+1]=='0')
{
dfs(w-1,h+1);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(a,'0',sizeof(a));
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)
{
char c;
cin >> c;
a[i][j] = c ;
}
}
// cout<<a[1][1];
dfs(0,0);
cout<<ans<<endl;
ans=0;
}
}