围棋算法

写在前面

围棋是世界范围内非常流行的棋类运动，是竞技体育项目。围棋的规则非常简单，做为编程初学者逻辑思维训练非常合适。

标准围棋棋盘是19行19列。为了简化起见，此处简化成9行9列。
标准围棋对弈方法是黑方和白方轮番下棋，为了简化，本算法引擎，支持任意的落子顺序，即落子顺序由程序输入
输入(棋子角色，棋子行号，棋子列号)
​ 1 2 3
表示白子放第2行第3列
2 3 3
表示黑子放第3行第3列
本算法引擎实现的是。从落子序列到棋盘状态的映射，当落子完成后，输出最终的棋盘状态。
+代表空白，o代表白棋，#代表黑棋
例如
1 1 1
1 1 2
1 2 1
1 2 2
输出
四颗白子形成的正方形状
围棋对战算法引擎需要实现各种围棋规则(提子，禁入点，反扑，劫)。具体的规则示意图请自行网上查阅。

样例

输入：

1 1 1
2 2 2

输出：

​ 1 2 3 4 5 6 7 8 9
1 o + + + + + + + +
2 + # + + + + + + +
3 + + + + + + + + +
4 + + + + + + + + +
5 + + + + + + + + +
6 + + + + + + + + +
7 + + + + + + + + +
8 + + + + + + + + +
9 + + + + + + + + +

逻辑思路

1. 输入数据后，判断该位置是否为空，空位可落子

2. 每次输入数据时调用jieInit（）函数初始化，（用一个数组单独记录棋盘上一轮被提走的棋子的位置）

3. 调用judgeLive（）函数判断自己落子的位置是否会处于自杀状态

   （1）如果是，则调用chessAnotherJudge（）函数判断周围是否有敌方棋子即将被杀（反扑）

   ​ a.如果是，则执行反扑chessAnotherClear（）（寻找并清除周围敌方濒死棋子）
   ​ b.如果否，则该点为禁入点，不可落子
   ​（2）如果否，则直接判断周围是否有敌方棋子即将被杀，并视情况执行清除敌方命令

4. 打劫，每次有棋子被提走后，jie[][]会记录提走的位置，并将记录保存到下一次输入后，在下一次输入判断时，会直接判断是否为劫

代码

> #include<iostream>
> using namespace std;
> /*---------------------全局变量------------------*/
> 
> int chessData[9][9];     //定义每个位置状态，0为空，1为白，2为黑
> const char chessChar[3]{ '+','o','#' };
> bool jie[9][9];
> 
> /*---------------------函数-------------------*/
> 
> /*打印棋盘*/
> void showChessBoard(void)
> {
> 	cout << "   ";
> 	for (int i = 0; i < 9; i++)
> 	{
> 		cout << "  " << i + 1;
> 	}
> 	cout << endl;
> 	for (int i = 0; i < 9; i++)
> 	{
> 		cout << " " << i + 1 << "   ";
> 		for (int j = 0; j < 9; j++)
> 		{
> 			int data = chessData[i][j];
> 			cout << chessChar[data] << "  ";
> 		}
> 		cout << endl;
> 	}
> }
> 
> /*寻找相反状态*/
> int anotherRole(int qi)
> {
> 	if (qi == 1)
> 		return 2;
> 	if (qi == 2)
> 		return 1;
> }
> 
> /*具体执行递归判定*/
> bool judgeNeigbourLive(int role, int x, int y, bool footprint[])
> {
> 	if (x < 0 || x >= 9 || y < 0 || y >= 9)//如果我超界，返回false
> 	{
> 		return false;
> 	}
> 	if (footprint[x * 9 + y] == true)      //如果我来过这个地方，返回false，不在判断
> 	{
> 		return false;
> 	}
> 	if (chessData[x][y] == 0)              //如果我为空，则邻居必定存活，即有气
> 	{
> 		return true;
> 	}
> 	if (chessData[x][y] == anotherRole(role))//如果我跟邻居的状态不同，则不判断
> 	{
> 		return false;
> 	}
> 
> 	footprint[x * 9 + y] = true;//每次判断完一个位置后就把该位置设为true，表示来过
> 
> 	//如果我跟邻居的状态相同，则递归判断邻居
> 	return judgeNeigbourLive(role, x - 1, y, footprint)
> 		|| judgeNeigbourLive(role, x + 1, y, footprint)
> 		|| judgeNeigbourLive(role, x, y - 1, footprint)
> 		|| judgeNeigbourLive(role, x, y + 1, footprint);
> }
> 
> /*递归判定是否存活*/
> bool judgeLive(int role, int x, int y)
> {
> 	bool footprint[9 * 9] = { false };  //用足迹记录下每一次走过的位置，避免重复判定引起无穷递归
> 	return judgeNeigbourLive(role, x - 1, y, footprint)
> 		|| judgeNeigbourLive(role, x + 1, y, footprint)
> 		|| judgeNeigbourLive(role, x, y - 1, footprint)
> 		|| judgeNeigbourLive(role, x, y + 1, footprint);
> } 
> 
> /*清除传入点周围的敌方棋子*/
> void chessClear(int qi, int x, int y) //递归寻找所有相同状态的点并将其提起
> {
> 	if (chessData[x - 1][y] == qi)
> 	{
> 		chessData[x - 1][y] = 0;
> 		jie[x - 1][y] = true;
> 		chessClear(qi, x - 1, y);
> 	}
> 	if (chessData[x + 1][y] == qi)
> 	{
> 		chessData[x + 1][y] = 0;
> 		jie[x + 1][y] = true;
> 		chessClear(qi, x + 1, y);
> 	}
> 	if (chessData[x][y - 1] == qi)
> 	{
> 		chessData[x][y - 1] = 0;
> 		jie[x][y - 1] = true;
> 		chessClear(qi, x, y - 1);
> 	}
> 	if (chessData[x][y + 1] == qi)
> 	{
> 		chessData[x][y + 1] = 0;
> 		jie[x][y + 1] = true;
> 		chessClear(qi, x, y + 1);
> 	}
> }
> 
> /*寻找传入点周围的濒死敌方棋子并提供信息给chessClear函数*/
> void chessAnotherClear(int x, int y) //判断落子后邻居是否存活，若死亡，则连片提子
> {
> 		if (judgeLive(chessData[x - 1][y], x - 1, y) == false)   //如果点左边不可存活，调用函数删除与该点连成片的所有点（上下左右）
> 		{
> 			chessClear(chessData[x - 1][y], x - 1, y);
> 			chessData[x - 1][y] = 0;
> 			jie[x - 1][y] = true;
> 		}
> 		if (judgeLive(chessData[x + 1][y], x + 1, y) == false)   //如果点右边不可存活，调用函数删除与该点连成片的所有点（上下左右）
> 		{
> 			chessClear(chessData[x + 1][y], x + 1, y);
> 			chessData[x + 1][y] = 0;
> 			jie[x + 1][y] = true;
> 		}
> 		if (judgeLive(chessData[x][y + 1], x, y + 1) == false)   //如果点上边不可存活，调用函数删除与该点连成片的所有点（上下左右）
> 		{
> 			chessClear(chessData[x][y + 1], x, y + 1);
> 			chessData[x][y + 1] = 0;
> 			jie[x][y + 1] = true;
> 		}
> 		if (judgeLive(chessData[x][y - 1], x, y - 1) == false)   //如果点下边不可存活，调用函数删除与该点连成片的所有点（上下左右）
> 		{
> 			chessClear(chessData[x][y - 1], x, y - 1);
> 			chessData[x][y - 1] = 0;
> 			jie[x][y - 1] = true;
> 		}
> }
> 
> /*判定传入点周围是否存在濒死敌方棋子*/
> bool chessAnotherJudge(int qi,int x, int y) 
> {
> 	if ((judgeLive(chessData[x - 1][y], x - 1, y) == false && chessData[x - 1][y]==anotherRole(qi))  //如果四周存在必死的棋子，且必死的棋子为敌方棋子，则返回1，表示这个位置可以落子
> 		|| judgeLive(chessData[x + 1][y], x + 1, y) == false && chessData[x + 1][y] == anotherRole(qi)
> 		|| judgeLive(chessData[x][y + 1], x, y + 1) == false && chessData[x][y + 1] == anotherRole(qi)
> 		|| judgeLive(chessData[x][y - 1], x, y - 1) == false && chessData[x][y - 1] == anotherRole(qi))
> 	{
> 		
> 		return 1;
> 	}
> 	else
> 		return 0;
> 	
> }
> 
> /*初始化jie数组*/
> void jieInit()
> {
> 	for (int i = 0; i < 9; i++)
> 	{
> 		for (int j = 0; j < 9; j++)
> 		{
> 			jie[i][j] = false;
> 		}
> 	}
> }
> 
> 
> /*----------------------主函数------------------------*/
> int main()
> {
> 	jieInit();
> 	int qi, x, y;
> 	for (; cin >> qi >> x >> y;)
> 	{
> 		if (chessData[x - 1][y - 1] == 0 && jie[x - 1][y - 1] == false)
> 		{
> 			jieInit();
> 			chessData[x - 1][y - 1] = qi;
> 			if (judgeLive(qi, x - 1, y - 1) == true) //如果自己可以存活
> 			{
> 				chessAnotherClear(x - 1, y - 1); //寻找并清除敌方无气子
> 			}
> 			if (judgeLive(qi, x - 1, y - 1) == false) //如果自己不可存活
> 			{
> 				if (chessAnotherJudge(qi,x - 1, y - 1) == 0) //如果周围可以存活，则禁入
> 				{
> 					chessData[x - 1][y - 1] = 0;
> 				}
> 				if (chessAnotherJudge(qi,x - 1, y - 1) == 1) //如果周围不可存活，则提子
> 				{
> 					chessAnotherClear( x - 1, y - 1);
> 				}
> 			}
> 		}
> 	}
> 	showChessBoard();
> }
> 
>