UVA1589 象棋 题解
0. 题目大意
在一个\(10\times9\)的网格上，可以游玩象棋。在本题中，我们考虑如下几个简化的规则：
- 每一个棋子下在交点上，一个交点不能同时有两个棋子；
- 棋盘的左上角为\((1,1)\)，右下角为\((10, 9)\)；
- 当一个棋子移动到它的敌人的棋子上，就说敌方的棋子要被“吃掉”。
当棋盘上的“将”有被敌人吃掉的风险，我们就说“照将”。当我们的玩家无论如何移动将的位置，都不能避免被敌人吃掉，我们就说“将死”。
简化一下，下面的 4 个棋子的情形如下：
- 帅，将（General, g)：将和帅可以横着或者竖着移动一格，并且正常情况下，无法离开“宫殿”（如原题PDF左上图）。一种特殊的情况是“飞将”。这是指两个将互相照面，中间没有其他的棋子相隔，我们可以让将离开它的宫殿吃掉对面的那个将。
- 车（Chariot, r)：车可以横着或者竖着走任意格，但是不能跳过中间的棋子。
- 炮（Cannon, c)：炮可以像车一样移动，但是能且仅能跳过一个中间相隔的棋子（无论这个棋子是我方的还是敌方的），吃掉下一个。
- 马（Horse, h)：马有8中跳法，如PDF中间图所示。但是，如果有一个棋子在马的周围一格远的话，马就不能往哪个方向跳了。这种情况叫做“别马腿”。
现在给你一个残局，仅仅由黑将，红将，以及若干个红色的车、马、炮组成。现在红方已经照将。写一个程序，看一看这个情况是不是已经将死了。
1. 初步分析
这是一道模拟的问题。简单的想法是：枚举这个将能够走的地方，并且判断是不是能够被吃掉。那么现在的问题转化为，给定一个残局，判定将能不能被吃掉。
要使得将被吃掉，有如下的几种情形：
- 出现了将帅照面（飞将）的情况；
- 被车吃掉；
- 被炮吃掉；
- 被马吃掉。
对于飞将的情况，主要看这是不是第一次移动。如果是的话，就不会被将死。代码中使用了WIN表示； 反之是LOSE。这有助于保持思路连贯清晰。
#define F(i, a, b) for(int i=a; i<=b; i++)
bool check(char arr[12][12], int x, int y, bool firstmv){
...
// Case 1. Is it a flying general?
F(i, x+1, 10){
char &curr = t[i][y];
if(curr!=0 && curr!='G') break;
if(curr == 'G') return firstmv;
}
...
}
由于马和炮都是形成十字形的内容，唯一的不同是中间间隔的棋子个数。所以我们可以同时处理他们。首先假设从当前点向上看有没有有威胁当前将的棋子，可以这样写：
int vskip = 0; // 跳过了几个子？
for(int i=x-1; i>=1; i--){
char &curr = t[i][y];
if(vskip == 0 && curr == 'R') return LOSE;
if(vskip == 1 && curr == 'C') return LOSE;
if(curr != 0) vskip++;
if(vskip >= 2) break; // 跳过2个，结束。
}
但是这样会有点麻烦。因为有4个方向。我们可以巧妙运用#define指令，来让我们的代码更可以阅读。首先对于循环做简化，分别表示正序和倒序循环：
#define F(i, a, b) for(int i=a; i<=b; i++)
#define Fd(i, a, b) for(int i=a; i>=b; i--)
然后设置宏定义：
#define SEARCH(dir, frm, to, current)\
{int vskip = 0;\
dir(i, frm, to){\
char &curr = current;\
if(vskip == 0 && curr == 'R') return LOSE;\
if(vskip == 1 && curr == 'C') return LOSE;\
if(curr != 0) vskip++;\
if(vskip >= 2) break;\
}}
之所以用大括号包围起来一层，是避免vskip被重复定义。这样一来，里面所有的参数就可以被替换了——因为C的#define是纯文本替换。我们调试起来就更容易了。具体地，我们只要写如下的代码：
SEARCH(Fd, x-1, 1, t[i][y]);
SEARCH(F, x+1, 10, t[i][y]);
SEARCH(Fd, y-1, 1, t[x][i]);
SEARCH(F, y+1, 9, t[x][i]);
就可以完成这样的功效了。
接下来考虑马可以威胁将的条件，简单画图，就可以写出如下的伪代码：
if(某个方向没有棋子别马腿){
if(能调过来的地方有马) return LOSE;
}
同样仿照上方的格式，就有
// Case 3. Finally check horse.
#define CHECK(blkx, blky, realx, realy)\
if(t[blkx][blky] == 0){\
if(t[realx][realy] == 'H') return LOSE;\
}
// up right
CHECK(x-1, y+1, x-1, y+2); CHECK(x-1, y+1, x-2, y+1);
// up left
CHECK(x-1, y-1, x-1, y-2); CHECK(x-1, y-1, x-2, y-1);
// down right
CHECK(x+1, y+1, x+1, y+2); CHECK(x+1, y+1, x+2, y+1);
// down left
CHECK(x+1, y-1, x+1, y-2); CHECK(x+1, y-1, x+2, y-1);
此外，还需要尝试每一个移动。这就可以移动整个数组。同样可以包装为一个简短的宏定义：
#define TRY_MOVE(tagx, tagy) \
{char tmpdst = b[tagx][tagy], tmpsrc=b[x][y];b[x][y] = 0; b[tagx][tagy]='g'; /*存起来*/\
if(IN_PALACE(tagx, tagy) && check(b, tagx, tagy, 0) == WIN){\
cout<<"NO"<<endl; \
return 0;}\
b[x][y] = tmpsrc, b[tagx][tagy]=tmpdst;} /*放回去*/
到此为止，我们就把大致的框架搭好了。
2. 代码
#include <iostream>
#include <cstring>
using namespace std;
#define N 12
#define F(i, a, b) for(int i=a; i<=b; i++)
#define Fd(i, a, b) for(int i=a; i>=b; i--)
#define IN_BOARD(x, y) (x>=1 && x<=10 && y>=1 && y<=9)
#define IN_PALACE(x, y) (x>=1 && x<=3 && y>=4 && y<=6)
#define WIN 1
#define LOSE 0
#define cerr if(0) cerr
char b[N][N];
bool check(char arr[12][12], int x, int y, bool firstmv){
// First copy arr to auxiliary arr t.
char t[N][N];
memcpy(t, b, sizeof(b));
// Case 1. Is it a flying general?
F(i, x+1, 10){
char &curr = t[i][y];
if(curr!=0 && curr!='G') break;
if(curr == 'G') return firstmv;
}
// Case 2. Eaten by a chaRiot or Cannon?
#define SEARCH(dir, frm, to, current)\
{int vskip = 0;\
dir(i, frm, to){\
char &curr = current;\
if(vskip == 0 && curr == 'R') return LOSE;\
if(vskip == 1 && curr == 'C') return LOSE;\
if(curr != 0) vskip++;\
if(vskip >= 2) break;\
}}
SEARCH(Fd, x-1, 1, t[i][y]);
SEARCH(F, x+1, 10, t[i][y]);
SEARCH(Fd, y-1, 1, t[x][i]);
SEARCH(F, y+1, 9, t[x][i]);
// Case 3. Finally check horse.
#define CHECK(blkx, blky, realx, realy)\
if(t[blkx][blky] == 0){\
if(t[realx][realy] == 'H') return LOSE;\
}
// up right
CHECK(x-1, y+1, x-1, y+2); CHECK(x-1, y+1, x-2, y+1);
// up left
CHECK(x-1, y-1, x-1, y-2); CHECK(x-1, y-1, x-2, y-1);
// down right
CHECK(x+1, y+1, x+1, y+2); CHECK(x+1, y+1, x+2, y+1);
// down left
CHECK(x+1, y-1, x+1, y-2); CHECK(x+1, y-1, x+2, y-1);
cerr<<"FINISH\n";
return !firstmv;
}
void visualize(bool aux_line){
if(aux_line){
for(int i=1; i<=9; i++){
cerr<<i<<" ";
}
cerr<<"\n";
}
for(int i=1; i<=10; i++){
for(int j=1; j<=9; j++){
if(b[i][j]==0){ cerr<<"+ ";}
else {cerr<<b[i][j]<<" ";}
}
cerr<<endl;
}
}
int work(){
int n, x, y;
cin>>n>>x>>y;
if(!n || !x || !y) return 1;
memset(b, 0, sizeof b);
b[x][y]= 'g';
while(n--){
char ch; int xi, yi;
cin>>ch>>xi>>yi;
b[xi][yi]=ch;
}
visualize(true);
// First check for initial case:
if(check(b, x, y, 1) == WIN) {cout<<"NO"<<endl; return 0;}
// Second, try every movement:
#define TRY_MOVE(tagx, tagy) \
{char tmpdst = b[tagx][tagy], tmpsrc=b[x][y];b[x][y] = 0; b[tagx][tagy]='g'; \
if(IN_PALACE(tagx, tagy) && check(b, tagx, tagy, 0) == WIN){\
cout<<"NO"<<endl; \
cerr<<"OK at "<<tagx<<" "<<tagy<<endl;\
return 0;}\
b[x][y] = tmpsrc, b[tagx][tagy]=tmpdst;}
TRY_MOVE(x+1, y); TRY_MOVE(x-1, y); TRY_MOVE(x, y+1); TRY_MOVE(x, y-1);
cout<<"YES"<<endl;
return 0;
}
int main(){
int ret=0;
do{
ret = work();
}while(ret != 1);
return 0;
}
注意：这里的调试信息使用了cerr输出。调试时候被宏定义为了if(0) cerr。