[第十四届蓝桥杯省B 岛屿个数]
小蓝得到了一副大小为
M
×
N
M×N
M×N 的格子地图，可以将其视作一个只包含字符
0
0
0（代表海水）和
1
1
1（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的
1
1
1 相连接而形成。
在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
.
.
.
,
(
x
k
−
1
,
y
k
−
1
)
(x_0,y_0),(x_1,y_1),...,(x_{k−1},y_{k−1})
(x0,y0),(x1,y1),...,(xk−1,yk−1)，其中 (xi+1%k ,yi+1 % k) 是由
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)，此时这 k 个格子就构成了一个 “环”。
如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。
若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿？
在进行统计时不需要统计子岛屿的数目。
输入格式 第一行一个整数 T，表示有 T 组测试数据。
接下来输入 T 组数据。
对于每组数据，第一行包含两个用空格分隔的整数 M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是 0 或 1。
输出格式 对于每组数据，输出一行，包含一个整数表示答案。
数据范围 对于 30% 的评测用例，1≤M,N≤10。 对于 100% 的评测用例，1≤T≤10，1≤M,N≤50。
输入样例：
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
输出样例：
1
3
样例解释 对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：
01111
11001
10201
10001
11111
岛屿 2 在岛屿 1 的 “环” 内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。
对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：
111111
100001
020301
100001
111111
注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有“环”。
代码
#include
#include
#include
#include
using namespace std;
const int N=15;
typedef pair
int a,b;
int g[N][N];
bool vis1[N][N],vis2[N][N];
//g陆地，vis1宽搜标记，vis2检查是否成环标记
void dfs(int x,int y){
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vis1[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>a||ny<1||ny>b||vis1[nx][ny]||g[nx][ny]==0) continue;
dfs(nx,ny);
}
}
bool check(int x,int y){
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
for(int i=0;i<8;i++){
int nx=x+dx[i],ny=y+dy[i];
if(g[nx][ny]||vis2[nx][ny]) continue;
if(nx<1||nx>a||ny<1||ny>b) return true;
vis2[nx][ny]=1;
if(check(nx,ny)) return true;
}
return false;
}
int main () {
int n;
cin>>n;
while(n--){
memset(g,0,sizeof g);
memset(vis1,0,sizeof vis1);
memset(vis2,0,sizeof vis2);
cin>>a>>b;
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++){
char x;cin>>x;
g[i][j]=x-'0';
}
int res=0;
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++){
if(g[i][j]&&vis1[i][j]==0){
vis1[i][j]=1;
dfs(i,j);
memset(vis2,0,sizeof vis2);
vis2[i][j]=1;
if(check(i,j)) res++;
}
}
cout< } return 0; } 推荐文章
发表评论