©2020-2024 ioDraw All rights reserved,
Privacy Policy
题目：
输入一个二维数组的row和col, 再输入这个二维数组，输出这个数组中包含的四连通块数量
四连通块是指一个数组数据, 其上下左右中有一个数字和它相等, 则这两个数连通, 属于一个连通块
示例输入：
7 7
0 0 0 0 0 0 0
0 1 1 1 1 2 0
0 3 3 1 2 2 0
0 4 3 1 2 2 0
0 5 5 5 5 0 0
0 5 6 6 6 6 0
0 0 0 0 0 0 0
示例输出：
the count of 4blocks is 7
算法：
初始化两张地图g_map和g_ergodic全为0，g_map写入数据，4连通块便是在g_map上，g_ergodic用于遍历，凡是遍历过的地方都置位-1，利用dfs深度优先算法，遍历g_map的时候对比g_ergodic的值，看是否已经遍历过，每一次遍历到一个新的值，g_map上相等的值对应位置的g_ergodic的值都会被遍历一遍(置为-1)，所以遍历g_map的时候发现对应位置的g_ergodic的值为0的话，即是找到了的新的连通块
源码：
#include <iostream> #include <vector> using namespace std; #define ROW 100
#define COL 100 int g_map[ROW][COL] = { 0 }; int g_ergodic[ROW][COL] = { 0 };
// 遍历 int g_count = 0; void draw_map(int row, int col) { if (row < 1 || col <
1) { cout << "输入不合法"; exit(1); } for (int i = 0; i < row; ++i) { for (int j =
0; j < col; ++j) { cin >> g_map[i][j]; } } } void dfs_4blocks(int x, int y, int
row, int col) { if (g_ergodic[x][y] == 0) { ++g_count; g_ergodic[x][y] = -1; }
if (y + 1 < col && g_map[x][y] == g_map[x][y + 1] && g_ergodic[x][y + 1] == 0)
{ g_ergodic[x][y + 1] = -1; dfs_4blocks(x, y + 1, row, col); } if (y - 1 >= 0
&& g_map[x][y] == g_map[x][y - 1] && g_ergodic[x][y - 1] == 0) { g_ergodic[x][y
- 1] = -1; dfs_4blocks(x, y - 1, row, col); } if (x + 1 < row && g_map[x][y] ==
g_map[x + 1][y] && g_ergodic[x + 1][y] == 0) { g_ergodic[x + 1][y] = -1;
dfs_4blocks(x + 1, y, row, col); } if (x - 1 >= 0 && g_map[x][y] == g_map[x -
1][y] && g_ergodic[x - 1][y] == 0) { g_ergodic[x - 1][y] = -1; dfs_4blocks(x -
1, y, row, col); } } int main() { int row, col; cin >> row >> col;
draw_map(row, col); for (int i = 0; i < row; ++i) { for (int j = 0; j < col;
++j) { dfs_4blocks(i, j, row, col); } } cout << "the count of 4blocks is " <<
g_count << endl; return 0; }