一、连通块算法题目描述

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

• 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

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