|
题目大意：
一个围棋盘的位置总共有三种状态，分别为空、白棋、黑棋，分别用0、1、2来表示。每一个位置都有上下左右四个邻居，当其邻居中有一个空格，则说明这个位置的棋子有气。当然，气是可以传递的，即只要一颗棋子它周围有气，则所有与该棋子相连的相同颜色的棋子都有气。若一个棋子的气为0，则该棋子将被吃掉。在下一个棋子时，若该棋子导致对方的某些棋子的气为0，则该将对方这些气为0的棋子吃掉，它们对应位置则需要被清空。若下棋子时不能导致对方棋子没气，却导致自己的棋子没气了，则这是一种自杀的行为，这种行为将不被允许。
现在假设棋盘大小为10x10，给定一个初始棋盘状态（保证该棋盘状态合法），然后不断的给定输入，每行输入为三个参数i，j，t，表示接下来要在位置i，j处下类型为t的棋子。要求写一个程序，针对每一行输出一个数值，表示这一步被吃掉的棋子个数。当被吃掉的棋子为白棋时，直接输出被吃掉的棋子的个数；若被吃掉的为黑棋，则输出被吃掉的棋的个数的负数；若此次为违规的自杀操作，则输出INT_MAX。
解析：
当给定一个输入时，我们首先判断下的这个棋子是否导致自身的棋子没气；然后判断下的这个棋子是否导致对方的棋子没气，并统计没气的棋子的个数；若对方没有棋子没气，但自身有棋子没气了，则为违规输入；否则，返回对方没气的棋子的个数即可。
那么这里关键问题便是如何判断是否有棋子没气了。这个问题可以用典型的dfs（深度优先）的方法来解决。给定一个位置以及该位置的棋子类型，我们首先判断该棋子上方是否为空，若为空，则表示与该棋子位置相连的相同棋子均有气；若上方棋子为相同颜色的棋子，则递归到该位置继续判断；若上方位置为对方棋子，则表示该棋子上方没有气。在遍历玩该棋子的上方能够遍历的位置之后，发现没有找到气，则选择其他方向继续遍历。知道一个方向找到了气，或是四个方向均没有气。
代码：
#include <iostream>
using namespace std;
//enum Type {AIR, WHITE, BLACK};
int A[10][10] =
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 2, 0, 0, 0, 0, 0,
0, 0, 0, 2, 1, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
bool B[10][10];
int eatCount = 0;
void initFlagMatrix()
{
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
B[i][j] = false;
}
}
bool hasAir(int i, int j, int type)
{
if(A[i][j] == 0) return true;
if(A[i][j] != type) return false;
eatCount++;
B[i][j] = true;
if(i > 0 && !B[i-1][j] && hasAir(i-1, j, type)) return true;
else if(i < 9 && !B[i+1][j] && hasAir(i+1, j, type)) return true;
else if(j > 0 && !B[i][j-1] && hasAir(i, j-1, type)) return true;
else if(j < 9 && !B[i][j+1] && hasAir(i, j+1, type)) return true;
else return false;
}
//将与A[i][j]相连的相同类型的棋子全部吃掉
void eatChess(int i, int j, int type)
{
if(A[i][j] != type) return;
A[i][j] = 0; //eat the chess
if(i > 0) eatChess(i-1, j, type);
if(i < 9) eatChess(i+1, j, type);
if(j > 0) eatChess(i, j-1, type);
if(j < 9) eatChess(i, j+1, type);
}
//check the whole chess of type is there any chess if out of air
bool hasAirOfType(int type, int &p, int &q)
{
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
{
if(A[i][j] != type || B[i][j]) continue;
eatCount = 0;
if(!hasAir(i, j, type))
{
p = i, q = j;
return false;
}
}
}
return true;
}
//get the chess that has been eaten when we put a chess of type on position [i,j]
int eatenChesscount(int i, int j, int type)
{
initFlagMatrix();
bool self_hasAir = hasAir(i, j, type);
eatCount = 0;
int p = 0, q = 0;
int other_type = (type==1?2:1);
initFlagMatrix();
bool other_hasAir = hasAirOfType(other_type, p, q);
if(!self_hasAir && other_hasAir)
{
A[i][j] = 0;
return INT_MAX; //suicide chess is not allowed
}
if(!other_hasAir)
{
eatChess(p, q, other_type);
if(other_type == 1) return eatCount;
else return 0-eatCount;
}
return 0;
}
void printChessState()
{
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
{
cout << A[i][j] << " ";
}
cout << endl;
}
}
int main()
{
int i, j, type;
while(cin >> i >> j >> type)
{
if(A[i][j] != 0)
{
cout << INT_MAX << endl;
continue;
}
A[i][j] = type;
printChessState();
cout << eatenChesscount(i, j, type) << endl;
printChessState();
}
}
|
转播
