UVa 1589

Xiangqi.cpp

#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

enum ChessBoardState
{
	Free,
	Obstacle
};

int horseMovebleDirectList[8][2] = {
	{ 1, -2 },  //{ 0, -1 }
	{ -1, -2 },
	{ -2, -1 },  //{ -1, 0 }
	{ -2, 1 },
	{ -1, 2 },  //{ 0, 1 }
	{ 1, 2 },
	{ 2, -1 },  //{ 1, 0 }
	{ 2, 1 },
};

int fourDirectionList[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 0, 1 },
	{ 1, 0 },
};

typedef struct tPosition
{
	int row;
	int col;
} Position;

int chessBoard[10][9];
vector<pair<char, Position>> chessList;

Position getNewPosition(Position &chessPosition, int rowMoveStep, int colMoveSetp)
{
	return Position{ chessPosition.row + rowMoveStep, chessPosition.col + colMoveSetp };
}

void initializeBoardAndChesses()
{
	chessList.clear();
	memset(chessBoard, ChessBoardState::Free, sizeof(chessBoard));
}

bool isInBlackGeneralMovingBoundary(Position &position)
{
	return 0 <= position.row && position.row <= 2 && 3 <= position.col && position.col <= 5;
}

bool isObstacle(Position &position)
{
	return 0 <= position.row && position.row < 10 && 0 <= position.col && position.col < 9 && chessBoard[position.row][position.col] != ChessBoardState::Free;
}

bool isSameRow(Position &position1, Position &position2)
{
	return position1.row == position2.row;
}

bool isSameCol(Position &position1, Position &position2)
{
	return position1.col == position2.col;
}

bool isSamePosition(Position &position1, Position &position2)
{
	return isSameRow(position1, position2) && isSameCol(position1, position2);
}

int countObstacleBetweenChessAndGeneral(Position &chessPosition, Position &newGeneralPosition)
{
	auto minRow = min<int>(chessPosition.row, newGeneralPosition.row);
	auto maxRow = max<int>(chessPosition.row, newGeneralPosition.row);
	auto minCol = min<int>(chessPosition.col, newGeneralPosition.col);
	auto maxCol = max<int>(chessPosition.col, newGeneralPosition.col);

	auto obstacleCount = 0;
	for (auto row = minRow; row <= maxRow; row++)
	{
		for (auto col = minCol; col <= maxCol; col++)
		{
			auto currentPosition = Position{ row, col };
			if (isObstacle(currentPosition) && !isSamePosition(currentPosition, newGeneralPosition))
			{
				obstacleCount++;
			}
		}
	}

	return obstacleCount - 1;  //don't counted current chess
}

bool checkEatableInChariotAttackArea(pair<char, Position> &chess, Position &newGeneralPosition)
{
	auto chessType = chess.first;
	auto chessPosition = chess.second;
	if (chessType != 'R') return false;

	return countObstacleBetweenChessAndGeneral(chessPosition, newGeneralPosition) == 0;
}

bool checkEatableInFlyingGeneralAttackArea(pair<char, Position> &chess, Position &newGeneralPosition)
{
	auto chessType = chess.first;
	auto chessPosition = chess.second;
	if (chessType != 'G') return false;

	return countObstacleBetweenChessAndGeneral(chessPosition, newGeneralPosition) == 0;
}

bool checkEatableInCannonAttackArea(pair<char, Position> &chess, Position &newGeneralPosition)
{
	auto chessType = chess.first;
	auto chessPosition = chess.second;
	if (chessType != 'C') return false;

	return countObstacleBetweenChessAndGeneral(chessPosition, newGeneralPosition) == 1;
}

bool checkEatableInHorseAttackArea(pair<char, Position> &chess, Position &newGeneralPosition)
{
	auto chessType = chess.first;
	auto chessPosition = chess.second;
	if (chessType != 'H') return false;

	for (auto direct = 0; direct < 8; direct++)
	{
		auto legPosition = getNewPosition(chessPosition, fourDirectionList[direct / 2][0], fourDirectionList[direct / 2][1]);
		auto attackPosition = getNewPosition(chessPosition, horseMovebleDirectList[direct][0], horseMovebleDirectList[direct][1]);
		if (!isObstacle(legPosition) && isSamePosition(attackPosition, newGeneralPosition))
		{
			return true;
		}
	}

	return false;
}

bool isCheckMate(Position &newGeneralPosition)
{
	for (auto &chess : chessList)
	{
		auto chessPosition = chess.second;
		if (isSamePosition(chessPosition, newGeneralPosition)) continue;
		if (checkEatableInHorseAttackArea(chess, newGeneralPosition)) return true;
		if (isSameRow(chessPosition, newGeneralPosition) || isSameCol(chessPosition, newGeneralPosition))
		{
			if (checkEatableInChariotAttackArea(chess, newGeneralPosition)) return true;
			if (checkEatableInFlyingGeneralAttackArea(chess, newGeneralPosition)) return true;
			if (checkEatableInCannonAttackArea(chess, newGeneralPosition)) return true;
		}
	}

	return false;
}

bool isEableDirectlyEatRedGeneral(Position &blackGeneralPosition)
{
	for (auto &chess : chessList)
	{
		auto chessPosition = chess.second;
		if (isSameCol(chessPosition, blackGeneralPosition) && checkEatableInFlyingGeneralAttackArea(chess, blackGeneralPosition))
		{
			return true;
		}
	}

	return false;
}

bool checkBlackGeneralAliveAfterMoved(Position &blackGeneralPosition)
{
	for (auto i = 0; i < 4; i++)
	{
		auto newBlackGeneralPosition = getNewPosition(blackGeneralPosition, fourDirectionList[i][0], fourDirectionList[i][1]);
		if (isInBlackGeneralMovingBoundary(newBlackGeneralPosition) && !isCheckMate(newBlackGeneralPosition))
		{
			return false;
		}
	}

	return true;
}

void inputChesses(int N)
{
	for (auto i = 0; i < N; i++)
	{
		char chessType[2];
		auto row = 0;
		auto col = 0;

		scanf("%s %d %d", &chessType, &row, &col);
		chessBoard[row - 1][col - 1] = ChessBoardState::Obstacle;
		chessList.push_back(make_pair(chessType[0], Position{ row - 1, col - 1 }));
	}
}

void solve(int blackGeneralRow, int blackGeneralCol)
{
	auto blackGeneralPosition = Position{ blackGeneralRow - 1, blackGeneralCol - 1 };
	if (isEableDirectlyEatRedGeneral(blackGeneralPosition))
	{
		puts("NO");
	}
	else
	{
		auto result = checkBlackGeneralAliveAfterMoved(blackGeneralPosition) ? "YES" : "NO";
		puts(result);
	}
}

int main()
{
	auto N = 0;
	auto blackGeneralRow = 0;
	auto blackGeneralCol = 0;
	while (~scanf("%d%d%d", &N, &blackGeneralRow, &blackGeneralCol))
	{
		if (N == 0 && blackGeneralRow == 0 && blackGeneralCol == 0)
		{
			break;
		}

		initializeBoardAndChesses();
		inputChesses(N);
		solve(blackGeneralRow, blackGeneralCol);
		getchar();  //empty line between two test cases
	}
	return 0;
}