本文主要是介绍P1141 01迷宫（dfs+染色联通块），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
染色联通块：
一个格联通的所有格
每个对应的最大可联通格子的个数均相同
分析：
1.只需要计算每个块里的元素个数
2.元素标记对应某个块
3.查找元素时：
由 （1）元素坐标->
（2）查找对应块的编号（visit[]查询）->
（3）输出对应块的元素个数(item[]查询)
代码如下：
#include<iostream>
using namespace std;int next1[5][3] = { {1,0},{-1,0},{0,1},{0,-1} };// 迷宫
char map[1009][1009] = {0};int visit[1009][1009] = { 0 };// 记录联通块记录的数量
int item[1000009] = { 0 }, k = 1;// 记录单个联通块的元素数量
int n = 1;// 矩阵的边长，查看的数量
int num = 0, check = 0;
void bfs(int x, int y);
int main()
{scanf("%d %d", &num, &check);for (int i = 0; i < num; i++){scanf("%s", map[i]);}// 如果map为0，即该点未有联通块for (int i = 0; i < num; i++){for (int j = 0; j < num; j++){if (!visit[i][j]){visit[i][j] = k; item[k] = 1;bfs(i, j);item[k] = n;k++; n = 1;}}}for (int i = 0; i < check; i++){int t1 = 0, t2 = 0;scanf("%d %d", &t1, &t2);cout << item[visit[t1 - 1][t2 - 1]] << endl;}return 0;
}
void bfs(int x, int y)
{for (int i = 0; i < 4; i++){ // 广度四个方向int tx = x + next1[i][0], ty = y + next1[i][1];// 数组溢出continueif (tx < 0 || tx >= num || ty < 0 || ty >= num) continue;// 该方向是一样，无法走continueif (map[x][y] == map[tx][ty]) continue;if (!visit[tx][ty]){// 标记坐标属于的联通块编号visit[tx][ty] = k;// 计算该联通块的元素数量n++;bfs(tx, ty);}}
}
这篇关于P1141 01迷宫（dfs+染色联通块）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
