首页 > 试题广场 >

围棋

[编程题]围棋
  • 热度指数:106 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
围棋是起源于中国有悠久历史的策略性棋类游戏。它的规则如下:
1. 棋盘19*19。
2. 棋子分黑白两色,双方各执一色。
3. 下法:每次黑或白着一子于棋盘的空点上。棋子下定后,不再向其他点移动。
4. 棋子的气:一个棋子在棋盘上,与它相邻的空点是这个棋子的“气”(这里相邻是指两个点有公共边)。 相邻的点上如果有同色棋子存在,这些棋子就相互连接成一个不可分割的整体,气合并计算。
相邻的点上如果有异色棋子存在,此处的气便不存在。
如果棋子所在的连通块失去所有的气,即为无气之子,不能在棋盘上存在。
5. 提子:把无气之子清理出棋盘的手段叫“提子”。提子有二种:
1) 着子后,对方棋子无气,应立即提取对方无气之子。
2) 着子后,双方棋子都呈无气状态,应立即提取对方无气之子。
6. 禁着点:棋盘上的任何一空点,如果某方在此下子,会使该子立即呈无气状态,同时又不能提取对方的棋子,这个点叫做“禁着点”,该方不能在此下子。
7. 禁止全局同形:无论哪一方,在成功进行了着子、提子操作后,棋盘局面不能和任何之前的局面相同。

你要做的是:输入一些操作,从空棋盘开始模拟这些操作。
对于每一步,若结果不正确,则输出对应的miss并且忽略这个操作,并在最后输出棋盘的局面。

输入描述:
第一行,测试数据组数≤100
第二行,每组测试数据,执行的步数 n ≤ 2000
然后 n 行
B x y
W x y
(1 ≤ x ≤ 19,1 ≤ y ≤ 19) 其中,二元组 x,y 表示围棋棋盘上第 x 行第 y 列对应的点。 输入数据保证是黑白轮流下的。


输出描述:
多行
对于miss的情况,输出是哪一种错误格式,其中:
miss 1 表示下的位置已经有棋了
miss 2 表示违反规则6
miss 3 表示违反规则7
对于正常的操作,不用输出。
最后输出最终盘面。“B表示黑子,W表示白子,如果是空点的话,就输出'.'字符。”
示例1

输入

1
12
B 1 3
W 1 2
B 2 4
W 2 1
B 1 1
W 2 3
B 3 3
W 3 2
B 1 1
W 2 3
B 2 2
W 2 3

对应的棋形是这样的:
<img src="https://uploadfiles.nowcoder.com/images/20170607/906271_1496803043049_ACDF8ED8821F13905E5C0A0E247B8C01" alt="" style="height:auto;width:138.6px;" />

输出

miss 2
miss 2
miss 1
miss 3
.WB................
WB.B...............
.WB................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................

好难啊

发表于 2018-03-08 21:50:55 回复(0)
#include <iostream>
#include <vector>
using namespace std;

void everyStep(int step, vector<vector<vector<char>>>& board);  //每一步棋执行的函数
bool breathlessOrNot(vector<vector<vector<char>>>& board, vector<vector<char>>& flag, int step, int i, int j); //判断该子是否无气
void setAlive(vector<vector<vector<char>>>& board, vector<vector<char>>& flag, int step, int i, int j);  //盘活该子以及所有相连同色子

int main()
{
int testTime;
cin >> testTime;
cin.get(); //吃掉回车

for (int t = 1; t <= testTime; t++)
{
int n;
cin >> n;  //每组测试步数
cin.get();
//三维数组记录每步的棋盘情况,棋盘的0行、列和20行、列不用,只是为了方便避免数组越界
vector<vector<vector<char>>> board(n, vector<vector<char>>(21, vector<char>(21, '.')));

for (int step = 0; step < n; step++) //每一步棋执行的函数
everyStep(step, board);

for (int i = 1; i <= 19; i++)  //每次测试最终输入棋盘局面
{
for (int j = 1; j <= 19; j++)
cout << board[n - 1][i][j];
cout << endl;
}
}
return 0;
}

//每一步棋执行的函数
void everyStep(int step, vector<vector<vector<char>>>& board)
{
//如果不是第一步(step!=0),先移植上一步的棋盘局面
if (step)
board[step] = board[step - 1];

char colorInput;
int rowInput, columnInput;
cin >> colorInput >> rowInput >> columnInput;
cin.get();

//判断落子处是否无子
if (board[step][rowInput][columnInput] == '.')
board[step][rowInput][columnInput] = colorInput;  //先落子
else
{
cout << "miss 1" << endl;
return;
}

char enemyColor;
if (colorInput == 'B')
enemyColor = 'W';
else
enemyColor = 'B';
vector<vector<char>> flag(21, vector<char>(21, 0)); //每一步的棋局都新建一个char型辅助二维数组来标记棋子是否有气(0表示未访问,1表示无气,2表示有气)

int enemyBreathless = 0; //是否有相邻敌子无气,值不是0则表示落子之后有敌子无气(但值并不是无气的敌子的数量)
bool thisBreathless = breathlessOrNot(board, flag, step, rowInput, columnInput); //判断该步落子是否无气

//判断周围敌子是否无气
for (int rowNextTo = rowInput - 1; rowNextTo <= rowInput + 1; rowNextTo += 2) //判断上下相邻的棋子
if (board[step][rowNextTo][columnInput] == enemyColor && flag[rowNextTo][columnInput] == 0) //相邻棋子是敌子且未被访问
if (breathlessOrNot(board, flag, step, rowNextTo, columnInput))
enemyBreathless++;

for (int colomnNextTo = columnInput - 1; colomnNextTo <= columnInput + 1; colomnNextTo += 2) //判断左右相邻的棋子
if (board[step][rowInput][colomnNextTo] == enemyColor && flag[rowInput][colomnNextTo] == 0)
if (breathlessOrNot(board, flag, step, rowInput, colomnNextTo))
enemyBreathless++;

//判断是否违反规则6:如果某方在此下子,会使该子立即呈无气状态,同时又不能提取对方的棋子,这个点叫做“禁着点”,该方不能在此下子。
if (thisBreathless && !enemyBreathless)
{
cout << "miss 2" << endl;
board[step] = board[step - 1];  //棋局恢复到上一步
return;
}
else if (enemyBreathless)  //如果敌子无气,则进行提子
{
for (int i = 1; i <= 19; i++)
for (int j = 1; j <= 19; j++)
if (board[step][i][j] == enemyColor && flag[i][j] == 1)
board[step][i][j] = '.';
}

//判断是否违反规则7:禁止全局同形:无论哪一方,在成功进行了着子、提子操作后,棋盘局面不能和任何之前的局面相同。
for (int preStep = step - 1; preStep >= 0; preStep--)
if (board[step] == board[preStep])
{
cout << "miss 3" << endl;
board[step] = board[step - 1];  //棋局恢复到上一步
return;
}
}

//判断该子是否无气
bool breathlessOrNot(vector<vector<vector<char>>>& board, vector<vector<char>>& flag, int step, int i, int j)
{
char thisColor = board[step][i][j];
if ((board[step][i - 1][j] == '.' && i - 1 >= 1) || (board[step][i + 1][j] == '.' && i + 1 <= 19) || (board[step][i][j - 1] == '.' && j - 1 >= 1) || (board[step][i][j + 1] == '.' && j + 1 <= 19))
{   //如果该子四周有气,则该子及其所有“相连”同色子都有气(flag置为2),同时return false;
setAlive(board, flag, step, i, j); //该子为第一个被发现有气的子,将该子及其所有相连同色子flag置为2,表示有气
return false;
}

flag[i][j] = 1;  //该子四周无气,先假设其无气(后面可能会被重新置为2)

for (int rowNextTo = i - 1; rowNextTo <= i + 1; rowNextTo += 2)  //判断上下相邻位置的同色子
if (board[step][rowNextTo][j] == thisColor && flag[rowNextTo][j] == 0)  //同色子要未被访问才执行后续判断
if (!breathlessOrNot(board, flag, step, rowNextTo, j))
return false;

for (int colomnNextTo = j - 1; colomnNextTo <= j + 1; colomnNextTo += 2) //判断左右相邻位置的同色子
if (board[step][i][colomnNextTo] == thisColor && flag[i][colomnNextTo] == 0)
if (!breathlessOrNot(board, flag, step, i, colomnNextTo))
return false;

return true;
}

//盘活该子以及所有相连同色子
void setAlive(vector<vector<vector<char>>>& board, vector<vector<char>>& flag, int step, int i, int j)
{
char thisColor = board[step][i][j];
flag[i][j] = 2;
for (int row = i - 1; row <= i + 1; row += 2)  //判断上下相邻位置
if (board[step][row][j] == thisColor && flag[row][j] != 2)
setAlive(board, flag, step, row, j);

for (int column = j - 1; column <= j + 1; column += 2) //判断左右相邻位置
if (board[step][i][column] == thisColor && flag[i][column] != 2)
setAlive(board, flag, step, i, column);
}
编辑于 2020-06-10 20:34:00 回复(0)

内存超限

发表于 2018-03-08 13:06:05 回复(0)

热门推荐

通过挑战的用户