一、连通块算法题目描述

连通块算法题目描述描述如下所示

• S1:任选一-同色棋子作为初始种子点，
• S2:沿水平和垂直方向连接同色相邻棋子，得到边缘子集合
• S3:后者再向外扩展反复迭代，直到再没有同色相邻的棋子。得到第一个连通块。
• 在剩下的同色棋子中任选-一个种子点，继续扩展，直到遍历所有同色棋子为止。得到所有连通块以后，再计算其相邻不重复的空位个数，得到该块的气数。

二、连通块算法文件结构

连通块算法文件结构如下所示

• 程序编写的头文件与源文件如下

三、连通块算法程序编写

3.1、连通块算法conBlock.h头文件内容

连通块算法conBlock.h头文件内容如下所示

#ifndef CONBLOCK_H
#define CONBLOCK_H
#include "mian.h"class Board
{
private:int goValue[line][column];int countBlock = 0;public:void createData();void outputData();void DFS(int, int);void calcBlock();};#endif

3.2、conBlock.cpp源文件内容

conBlock.cpp源文件内容如下所示

#include "conBlock.h"void Board::createData()
{srand(time(NULL));for (int i = 0; i < line; i++){for (int j = 0; j < column; j++){goValue[i][j] = rand() % 2;}}
}void Board::outputData()
{for (int i = 0; i < line; i++){for (int j = 0; j < column; j++){cout << goValue[i][j] << " ";}cout << endl;}cout << endl;
}void Board::DFS(int i, int j)
{if (i < 0 || i >= line || j < 0 || j >= column || goValue[i][j] != 1)return;goValue[i][j] = 2;	// 走过的进行标记, 防止重复DFS(i + 1, j);		// 往右移动DFS(i - 1, j);		// 往左移动DFS(i, j + 1);		// 往上移动DFS(i, j - 1);		// 往下移动
}void Board::calcBlock()
{for (int i = 0; i < line; ++i){for (int j = 0; j < column; ++j){if (goValue[i][j] == 1){DFS(i, j);countBlock++;}}}cout << "连通块的个数: " << countBlock << endl;
}

3.3.3、mian.h头文件内容

mian.h头文件内容如下所示

#ifndef MAIN_H
#define MAIN_H#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;#define line 19
#define column 19#endif

3.3.4、main.cpp源文件内容如下

main.cpp源文件如下所示

#include "mian.h"
#include "conBlock.h"int main()
{system("color 3E");Board board;board.createData();cout << "棋盘如下 1代表白棋 0代表黑棋\n计算白棋的连通块数" << endl;board.outputData();board.calcBlock();system("pause");return 0;
}

四、连通块算法程序运行结果

连通块算法程序运行结果如下所示