当前位置：首页 > 编程日记 > 正文

分别用BFS和DFS求给定的矩阵中“块”的个数

编程日记 2024-09-07 05:30:00

背景介绍

BFS实现

基本思想

获取相邻位置元素技巧

BFS函数

DFS实现

基本思想

DFS函数

完整代码

背景介绍

背景

给出一个mxn的矩阵，矩阵中的元素为0或1。称位置(x,y)与其上下左右四个位置(x,y+1),(x,y-1),(x-1,y),(x+1,y)是相邻的。如果矩阵中有若干(可以是1)个1是相邻的(不必两两相邻)，那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。

例子

0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

上面给定的6x7的矩阵中块的个数是4。

BFS实现

基本思想

枚举每一个位置的元素，如果为0，则跳过；如果为1，则使用BFS查询与该位置相邻的4个位置(前提是不出界)，判断它们是否为1(如果某个相邻的位置为1，则同样去查询与该位置相邻的4个位置，直到整个“1”块访问完毕)。而为了防止走回头路，一般可以设置一个bool型数组inq(即in queue的简写)来记录每个位置是否在BFS中已入过队(不是是否已被访问)。

获取相邻位置元素技巧

增量数组+遍历

int X[] = {0,0,-1,1};
int Y[] = {1,-1,0,0};for(int i=0;i<4;i++){newX = nowX + X[i];newY = nowY + Y[i];
}

BFS函数

//BFS的作用是访问(x,y)所在块中的所有结点
//具体访问操作是将inq[x][y]设置为1 
void BFS(int x,int y){queue<Node> que;node.x = x,node.y = y;//当前节点的坐标是(x,y)que.push(node);//头结点入队inq[x][y] = true;//设置已经入队while(!que.empty()){Node top = que.front();//取出队首元素que.pop();//队首元素出队for(int i=0;i<4;i++){int newX = top.x + X[i];int newY = top.y + Y[i];if(judge(newX,newY)){//如果该邻居节点可以入队 node.x = newX;node.y = newY;que.push(node);//入队inq[newX][newY] = true;//设置已经入队 }} } 
}

DFS实现

基本思想

DFS和BFS函数的作用相同。只不过不再需要队列，而是使用递归。关键步骤是，遇到符合要求的邻居结点，进一步看邻居的邻居是否符合要求。

DFS函数

//DFS的作用是访问(x,y)所在块中的所有节点
//具体访问操作是将inq[x][y]设置为1
void DFS(int x,int y){inq[x][y] = true;//设置(x,y)被访问过for(int i=0;i<4;i++){int newX = x + X[i];int newY = y + Y[i];if(judge(newX,newY)){//如果该邻居节点可以入队 inq[newX][newY] = true;DFS(newX,newY);//进一步搜索邻居的邻居 }} 
}

完整代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>using namespace std;const int maxn = 100;struct Node{int x,y;//坐标(x,y) 
}node;int n,m;//矩阵的大小是n*m
int matrix[maxn][maxn];//01矩阵
bool inq[maxn][maxn] =  {false};//初始化为全部没入过队列
int X[4] = {0,0,-1,1};//增量数组
int Y[4] = {1,-1,0,0};	 bool judge(int x,int y){//判断位置(x,y)是否可以入队//越界，不入if(x>=n||x<0||y>=m||y<0)return false;//为0，不入 if(!matrix[x][y])return false;//已经入过，不入if(inq[x][y])return false;return true;
}//BFS的作用是访问(x,y)所在块中的所有结点
//具体访问操作是将inq[x][y]设置为1 
void BFS(int x,int y){queue<Node> que;node.x = x,node.y = y;//当前节点的坐标是(x,y)que.push(node);//头结点入队inq[x][y] = true;//设置已经入队while(!que.empty()){Node top = que.front();//取出队首元素que.pop();//队首元素出队for(int i=0;i<4;i++){int newX = top.x + X[i];int newY = top.y + Y[i];if(judge(newX,newY)){//如果该邻居节点可以入队 node.x = newX;node.y = newY;que.push(node);//入队inq[newX][newY] = true;//设置已经入队 }} } 
}//DFS的作用是访问(x,y)所在块中的所有节点
//具体访问操作是将inq[x][y]设置为1
void DFS(int x,int y){inq[x][y] = true;//设置(x,y)被访问过for(int i=0;i<4;i++){int newX = x + X[i];int newY = y + Y[i];if(judge(newX,newY)){//如果该邻居节点可以入队 inq[newX][newY] = true;DFS(newX,newY);//进一步搜索邻居的邻居 }} 
} int main(){scanf("%d%d",&n,&m);for(int x=0;x<n;x++){for(int y=0;y<m;y++){scanf("%d",&matrix[x][y]);}}int num = 0;//块数for(int x=0;x<n;x++){for(int y=0;y<m;y++){//如果元素为1且没如果队，那就是发现了一个新块 if(matrix[x][y]&&!inq[x][y]){num ++;DFS(x,y);} }} printf("%d\n",num);	return 0;
}

https://www.dkcj.cn/info/17638.html

背景介绍

BFS实现

基本思想

获取相邻位置元素技巧

BFS函数

DFS实现

基本思想

DFS函数

完整代码

相关文章：