信息学奥赛一本通 1329例8.2细胞
【题目链接】
【题目考点】
1. 搜索 连通块问题
【解题思路】
设数组vis
,vis[i][j]
表示(i,j)位置已经访问过。
遍历地图中的每个位置,尝试从每个位置开始进行搜索。
如果该位置不是0且没有访问过,那么访问该位置,并尝试从其上下左右四个位置开始搜索。
在看一个新的位置时,如果该位置在地图内,没有访问过且不是0,那么继续从该位置开始进行搜索。
在遍历网格的过程中,一次成功开始的搜索可以确定一个连通块,统计连通块的个数,即为结果。
搜索方法可以采用深搜或广搜。
【题解代码】
解法1:深搜
#include<bits/stdc .h>
using namespace std;
#define N 105
int n, m, ct, dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//dir:方向数组
char mp[N][N];//地图
bool vis[N][N];//vis[i][j]:(i,j) 位置是否已访问过
void dfs(int sx, int sy)//尝试从(sx,sy)位置开始进行深搜
{
for(int i = 0; i < 4; i)//遍历上下左右四个方向
{
int x = sx dir[i][0], y = sy dir[i][1];//新位置(x,y)
if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && mp[x][y] != '0')//如果(x,y)在地图内,未访问过,且不是'0',则从该位置开始进行深搜
{
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i)
for(int j = 1; j <= m; j)
cin >> mp[i][j];
for(int i = 1; i <= n; i)
for(int j = 1; j <= m; j)
{//尝试从每个位置开始进行深搜
if(vis[i][j] == false && mp[i][j] != '0')
{
vis[i][j] = true;
dfs(i, j);
ct ;//连通块个数加1
}
}
cout << ct;
return 0;
}
解法2:广搜
#include<bits/stdc .h>
using namespace std;
#define N 105
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
int n, m, ct, dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//dir:方向数组
char mp[N][N];//地图
bool vis[N][N];//vis[i][j]:(i,j) 位置是否已访问过
void bfs(int sx, int sy)//尝试从(sx,sy)位置开始进行广搜
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy));
while(que.empty() == false)
{
Node u = que.front();
que.pop();
for(int i = 0; i < 4; i)//遍历上下左右四个方向
{
int x = u.x dir[i][0], y = u.y dir[i][1];//新位置(x,y)
if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && mp[x][y] != '0')
{
vis[x][y] = true;//访问(x,y)位置
que.push(Node(x, y));//(x,y)入队
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i)
for(int j = 1; j <= m; j)
cin >> mp[i][j];
for(int i = 1; i <= n; i)
for(int j = 1; j <= m; j)
{//尝试从每个位置开始进行广搜
if(vis[i][j] == false && mp[i][j] != '0')
{
bfs(i, j);
ct ;
}
}
cout << ct;
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfebji
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01