C++广度优先算法应用题——计算岛屿面积
测试数据如下：
6 6 3 4
0 1 0 1 1 0
0 0 0 1 1 1
1 0 1 1 0 1
0 0 0 1 0 0
0 1 1 1 1 0
0 0 0 0 0 0
//Author:PanDaoxi
#include <iostream>
using namespace std;
//定义结构体
struct node{
int x,y;
}que;
int head=1,tail=1;
//头指针、尾指针分别对应当前搜索对象的下标和下个元素的位置
int m,n,x,y,map; //m,n地图行、列 x,y小童位置的坐标
int sum=0; //计数器：岛屿的面积
//搜索方向
int next={{-1,0},{0,1},{1,0},{0,-1}};
void bfs(){
//第一个搜索的点
que.x=x;
que.y=y;
map=0;
tail++;
//更新岛屿面积
sum++;
//广搜核心代码
while(head<tail){
for(int i=0;i<=3;i++){
int tx=que.x+next,
ty=que.y+next;
//判断是否可以通过
if(tx<1||tx>m||ty<1||ty>n) continue;
//判断是否为陆地
if(map==1){
que.x=tx;
que.y=ty;
tail++;
map=0;
sum++;
}
}
//搜索完以后
head++;
}
}
int main(){
//输入地图行列、小童的坐标
cin>>m>>n>>x>>y;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>map;
}
}
//广度优先搜索
bfs();
//输出信息
cout<<sum<<endl;
return 0;
}
https://blog.51cto.com/u_15467636/4863147
页:
[1]