【题目链接】
【题目考点】
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; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/97668.html