1335：【例2-4】连通块_1335:【例2-4】连通块

【算法分析】

       设数组vis，vis[i][j]表示(i,j)位置已经访问过。遍历地图中的每个位置，尝试从每个位置开始进行搜索。如果该位置不是0且没有访问过，那么访问该位置，并尝试从其上下左右四个位置开始搜索。在看一个新的位置时，如果该位置在地图内，没有访问过且不是0，那么继续从该位置开始进行搜索。在遍历网格的过程中，一次成功开始的搜索可以确定一个连通块，统计连通块的个数，即为结果。 

现在我们以样例为例模拟出这个方格图的搜索顺序：    
①将(1,1)加入队列，(1,1)表示左上角这个格子，当前队列为：{(1,1)}，联通块加1,等于1。    
②取出队首的(1,1)，标记为已搜索并对其进行四连通扩展，扩展出(1,2)，删除(1,1),队列变为：{(1,2)}。    
③取出队首的(1,2)，标记为已搜索并对其进行四连通扩展，扩展到了(1,1)，(1,3)，(2,2)，(1,1)已经被标记搜索过，所以只将(1,3)，(2,2)加入队列，删除队首(1,2),队列变为：{(1,3)，(2,2)}。    
④取出队首的(1,3)，没有扩展出新格子，删除队首队列变为：{(2,2)}    
⑤取出队首的(2,2)，没有扩展出新格子，队列变为{}。完成以(1,1)开始的搜索。    
⑥将(3,1)加入队列，队列变为：{(3,1)}，联通块数加1变为2。    
⑦取出队首的(3,1)，没有扩展出新格子，删除队首队列变为{}。完成以(3,1)开始的搜索。    
⑧将(3,3)加入队列，队列变为：{(3,3)}，联通块数加1变为3。    
⑨取出队首的(3,3)，没有扩展出新格子，删除队首队列变为{}。完成以(3,3)开始的搜索。无法再加入新的元素，程序结束。
搜索方法可以采用深搜或广搜。

广搜代码

#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, a[N][N], ans;//ans:连通块个数
bool vis[N][N];//vis[i][j]:(i,j)是否访问过 
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void bfs(int sx, int 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];
			if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && a[x][y] == 1)
			{
				vis[x][y] = true;
				que.push(Node(x,y));
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			if(a[i][j] == 1 && vis[i][j] == false)//如果这里是黑色的且没访问过 
			{
				bfs(i, j);
				ans++;//每次成功进行广搜可以确定一个连通块 
			}
		}
	cout << ans;
	return 0;
}

解析：
struct Node {    
int x, y;    
Node(){}    
Node(int a, int b):x(a),y(b){}
};

这是一个 C++ 中的结构体定义。该结构体名为 Node，包含两个成员变量 x 和 y，均为整型。同时定义了两个构造函数，一个是默认构造函数，一个是带两个参数的构造函数，用于初始化 x 和 y。可以在程序中使用 Node 类型来创建变量。例如：Node n(1, 2); // 创建一个 Node 变量 n，其 x 值为 1，y 值为 2