BFS广搜例题,问题引入 --- 阿狗荒岛逃生系列(其一)

该例题来自我的学长,感谢学长们对我的带领:

例题简述:

代码及详细注释:

#include<bits/stdc++.h>
using namespace std;

struct Node{
int x,y;
};

int n,m;
int Map[31][31];//用来存图;
int vis[31][31];//在搜索父点的四个方向时用来防止某个方向走过;
int sum; //用来记录岛的大小;

void BFS(Node start){
queue<Node> q;
//在这里用二维数组表示4个方向
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
//把起点加入队列
q.push(start);
//判空,q为空时q.empty()返回1(true),否则返回0(false);
while(!q.empty()){
//取队首元素进行扩展;
Node t=q.front();
//弹出队首元素;
q.pop();
//四个方向遍历;
for(int i=0;i<4;i++){
//定义一个now结构体来存当前方向的坐标;
Node now;
now.x=t.x+dir[i][0];//t.x为父点,循环不断的 进行,dir[i][0]分别为:0,1,0,-1;
now.y=t.y+dir[i][1];// t.y为父点,循环不断的 进行,dir[i][1]分别为:1,0,-1,0;
//下一步如果是海,跳过;
if(now.x<0 || now.x>n-1 || now.y<0 || now.y>m-1)
continue;
//开始时在主函数中vis已经被初始化为零了;
//如果vis为零(没有走过)并且当前位置为1(若不是海)执行里面的语句;
if(!vis[now.x][now.y] && Map[now.x][now.y]==1){
//把该位置用vis标记为1(标记为走过),
vis[now.x][now.y]=1;
//将该位置入队;
q.push(now);
//sum加1,记录陆地的面积;
sum++;
}
}
}
}

int main(){
//定义一个s结构体用来记录阿狗掉落的位置(起始点);
Node s;
//输入岛的尺寸;
while(cin>>n>>m){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
//存图;
cin>>Map[i][j];
//输入阿狗掉落的地点(起始点)
cin>>s.x>>s.y;
//海的地方用零来表示,故,掉落地点为零即开始就掉水里了;
if(Map[s.x][s.y]==0)
cout<<"阿狗掉到水里了,悲剧 ~ ";
//把vis数组(用来判断重复道路的数组)初始化;
memset(vis,0,sizeof(vis));
//用sum来记录岛的面积,初始化为零;
sum=0;
//把掉落点传到 BFS函数里;
BFS(s);
//输出岛的面积;
cout<<sum<<" ";
}
return 0;
}

原文地址:https://www.cnblogs.com/sunowsir/p/6696442.html