这道题也是bfs算周长,如果用dfs需要回溯
1、条件准备
graph数组存图,visit数组判断是否走过
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'
int dir[4][2]={1,0,0,1,-1,0,0,-1};
bool graph[55][55];
bool visit[55][55];
int n,m;
2、主函数
先存图,然后遍历一遍,找到岛屿进入bfs并输出返回
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
rep(i,1,n)
rep(j,1,m)
cin>>graph[i][j];
rep(i,1,n)
rep(j,1,m)
if(graph[i][j])
{cout<<bfs(i,j);return 0;}
return 0;
}
3、bfs算法
先把起始点存进来,num存边数。
然后遍历岛屿每个点,把没走过的放进来。
对于每个点,看它们四周是否为水,是就num++.
最后返回num
int bfs(int x,int y)
{
queue<pair<int,int>> q;
q.push({x,y});
visit[x][y]=1;
int num=0;
while(!q.empty())
{
pair<int,int> cur=q.front();
for(int i=0;i<4;i++)
{
int xx=cur.first+dir[i][0],yy=cur.second+dir[i][1];
if(graph[xx][yy]&&!visit[xx][yy])
{
q.push({xx,yy});
visit[xx][yy]=1;
}
if(!graph[xx][yy])num++;
}
q.pop();
}
return num;
}
4、总结
这道题也算较为容易的搜索题
完整代码如下:
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
#define endl '\n'
int dir[4][2]={1,0,0,1,-1,0,0,-1};
bool graph[55][55];
bool visit[55][55];
int n,m;
int bfs(int x,int y)
{
queue<pair<int,int>> q;
q.push({x,y});
visit[x][y]=1;
int num=0;
while(!q.empty())
{
pair<int,int> cur=q.front();
for(int i=0;i<4;i++)
{
int xx=cur.first+dir[i][0],yy=cur.second+dir[i][1];
if(graph[xx][yy]&&!visit[xx][yy])
{
q.push({xx,yy});
visit[xx][yy]=1;
}
if(!graph[xx][yy])num++;
}
q.pop();
}
return num;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
rep(i,1,n)
rep(j,1,m)
cin>>graph[i][j];
rep(i,1,n)
rep(j,1,m)
if(graph[i][j])
{cout<<bfs(i,j);return 0;}
return 0;
}