C语言 | 算法 | BFS

1.BFS思想

DFS是“一条路走到黑”，而BFS则是“以中心层层向外扩散”。

BFS：从图的某一结点出发，首先依次访问该结点的所有邻接结点，再按这些邻接结点被访问的先后次序依次访问与它们相邻接的所有未被访问的结点，重复此过程，直到所有结点被访问完为止。

2.求矩阵中“块”的个数

题目：

给出一个 m x n 的矩阵，矩阵中的元素为0或1。如果矩阵中有若干个 1是相邻的，那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。例如以下的 6 x 7的矩阵中，“块”的个数为4。

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

分析：

• 枚举每个位置的元素，如果为0，则跳过；如果为1，则使用BFS查询与该位置相邻的4个位置（不出界的考虑），判断它们是否为1，若存在为1，则以该位置为中心构成一个“块”。对于它周围为1的位置，则同样用BFS查询与该位置相邻的4个位置，直到1都被访问完为止。为了防止走“回头路”，即防止同一个元素被访问两次及以上，应该设置一个数组，来记录访问过的（入过队的）元素，对于这些入过队的1，下次遇见和0一样，直接跳过。

• 设置两个增量数组，便于表示当前位置的相邻的上下左右四个位置：(x,y+1) (x,y-1) (x+1,y) (x-1,y)

  int X[] = {
       0,0,1,-1};
  int Y[] = {
       1,-1,0,0};
  1
  2
  3
  4

  此后可用for循环来枚举4个方向：

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

#include<iostream>
#include<queue>
using namespace std;
const int maxn = 100;
struct node {
   
	int x, y; //（x,y）
}Node;
int n, m; //n*m矩阵，用于获取用户输入
int matrix[maxn][maxn] = {
    0 }; //实际开辟的数组
bool inq[maxn][maxn] = {
    false }; //inq(in queue缩写，为true时表示已入过队)
//设置两个增量数组
int X[4] = {
    0,0,1,-1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15