华为2014校园招聘笔试，围棋吃子判断

题目大意：

一个围棋盘的位置总共有三种状态，分别为空、白棋、黑棋，分别用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();
 }
}