题解 UVa1589 象棋
BeiDAmen_Linyu · · 题解
题意简述：
题目链接：UVa1589 象棋
给出一个中国象棋的残局，红方有帅 (G)，车 (R)，马 (H)，炮 (C) 四种棋子，黑方只有一个将且已被将军，要求判断黑方是否已被将死，需要考虑 “ 蹩马脚 ” 和 “ 将帅照面 ” 。
分析：
很容易可以想到用二维数组模拟棋盘，标记红方可以攻击到的位置。
把棋盘上的点分为以下 4 类：
-1 --- 代表该位置在红方的攻击范围内。
0 --- 代表该位置安全。
1 --- 代表该位置有红方棋子，且黑方吃掉该子后会进入红方的攻击范围。
2 --- 代表该位置有红方棋子，但黑方吃掉该子后是安全的。
然后分析红方四种棋子的进攻方式：
帅 (G)：向正上方直线进攻，直到遇到另一枚棋子。
车 (R)：向上下左右四个方向进攻，直到遇到另一枚棋子。
炮 (C)：向四个方向进攻，范围为中途遇到的第一个和第二个棋子之间。
马 (H): 走日字进攻，考虑蹩马脚。
发现车和炮的进攻方式很相似，唯一的区别是经过的棋子数，车的攻击范围可以看作经过的第 0 个棋子到第 1 个棋子之间，炮则是第 1 个和第 2 个之间，因此我们可以把他们写进同一个函数，用一个参数代表初始棋子数，车为 1，炮为 0。
需要注意的是车和炮经过的最后一个棋子也在他们的攻击范围之内，所以下面 3 个 if 的顺序不能反。
int d[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
void RunCar(int isr, int x, int y) { //isr意义见上
for (int i = 0; i < 4; i++) {
int k = isr, dx = x + d[i][0], dy = y + d[i][1];
while (dx <= 10 && dx >= 1 && dy <= 9 && dy >= 1) {
if (k) {
if (board[dx][dy] < 1) board[dx][dy] = -1; //该位置无棋子
else board[dx][dy] = 1; //有棋子
}
if (board[dx][dy] > 0) k++;
if (k == 2) break; //注意顺序
dx += d[i][0], dy += d[i][1];
}
}
}然后我们发现其实帅也可以以车的方式用这个函数标记攻击范围，因为黑方的将不可能在帅的左、右或后方，这些位置究竟能不能被攻击并不重要。
然后就只剩下马了，马的攻击范围是八个点，而且要判断蹩马脚的情况，看上去好像很麻烦，只能使用复制 - 粘贴大法，实际上我们可以选择扩展上面使用的方向数组，以简化代码，方便调试 ( 好像也不是很方便 ) 。
int d[4][4] = { {1, 0, 0, 1}, {-1, 0, 0, 1}, {0, 1, 1, 0}, {0, -1, 1, 0} };
void Horse(int x, int y) {
for (int i = 0; i < 4; i++) {
int dx = x + d[i][0], dy = y + d[i][1];
if (board[dx][dy] < 1 && dx <= 10 && dx >= 1 && dy <= 9 && dy >= 1) {
dx += d[i][0], dy += d[i][1];
//因为懒没有判出界，这里判不判都一样
int ddx = dx + d[i][2], ddy = dy + d[i][3];
if (board[ddx][ddy] > 0) board[ddx][ddy] = 1;
else board[ddx][ddy] = -1;
ddx = dx - d[i][2], ddy = dy - d[i][3];
if (board[ddx][ddy] > 0) board[ddx][ddy] = 1;
else board[ddx][ddy] = -1;
}
}
}其中 board[dx][dy] < 1 为判断蹩马脚。
接下来判断黑方将的走位，这部分比较简单，略。
这题算是个不错的练习，建议独立编写完整代码。
上完整 AC 代码：
#include <cstdio>
#include <cstring>
struct piece{
int x, y;
char type;
} red[10];
int board[12][12];
int gx, gy, n;
int d[4][4] = { {1, 0, 0, 1}, {-1, 0, 0, 1}, {0, 1, 1, 0}, {0, -1, 1, 0} };
void RunCar(int isr, int x, int y) {
for (int i = 0; i < 4; i++) {
int k = isr, dx = x + d[i][0], dy = y + d[i][1];
while (dx <= 10 && dx >= 1 && dy <= 9 && dy >= 1) {
if (k) {
if (board[dx][dy] < 1) board[dx][dy] = -1;
else board[dx][dy] = 1;
}
if (board[dx][dy] > 0) k++;
if (k == 2) break;
dx += d[i][0], dy += d[i][1];
}
}
}
void Horse(int x, int y) {
for (int i = 0; i < 4; i++) {
int dx = x + d[i][0], dy = y + d[i][1];
if (board[dx][dy] < 1 && dx <= 10 && dx >= 1 && dy <= 9 && dy >= 1) {
dx += d[i][0], dy += d[i][1];
int ddx = dx + d[i][2], ddy = dy + d[i][3];
if (board[ddx][ddy] > 0) board[ddx][ddy] = 1;
else board[ddx][ddy] = -1;
ddx = dx - d[i][2], ddy = dy - d[i][3];
if (board[ddx][ddy] > 0) board[ddx][ddy] = 1;
else board[ddx][ddy] = -1;
}
}
}
//void printboard() {
// for (int i = 1; i <= 10; i++) {
// for (int j = 1; j <= 9; j++) printf("%4d", board[i][j]);
// putchar('\n');
// }
//}
int main() {
while (scanf("%d%d%d", &n, &gx, &gy) == 3 && n && gx && gy) {
memset(board, 0, sizeof(board));
for (int i = 1; i <= n; i++) {
scanf("\n%c %d %d", &red[i].type, &red[i].x, &red[i].y);
//scanf读入字符和字符串一向比较麻烦，这里数据量不大其实cin更好
board[red[i].x][red[i].y] = 2;
}
for (int i = 1; i <= n; i++) {
if (red[i].type == 'G') RunCar(1, red[i].x, red[i].y);
if (red[i].type == 'R') RunCar(1, red[i].x, red[i].y);
if (red[i].type == 'C') RunCar(0, red[i].x, red[i].y);
if (red[i].type == 'H') Horse(red[i].x, red[i].y);
}
bool survival = false;
// printboard();
for (int i = 0; i < 4; i++) {
int dx = gx + d[i][0], dy = gy + d[i][1];
if (dx >= 1 && dx <= 3 && dy >= 4 && dy <= 6) //黑将移动范围
if (board[dx][dy] == 2 || board[dx][dy] == 0) survival = true;
}
if (survival) printf("NO\n");
else printf("YES\n");
}
return 0;
}