XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 4-1UVa1589 - Xiangqi

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 4.7k 阅读时长 ≈ 4 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，0 ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//UVa1589
#include<iostream>
#include<cmath>
#define P(x,y) Pi[x].position[y]
using namespace std;
int N;//2<=N<=7
bool A[4];//around,储存"将"周围是不是已经不能走了  0上 1左 2下 3右
struct piece {
	char name;
	int position[2];//0x 1y
}Pi[10];

inline bool f1(int i, int j, bool po) {//判断第j个子是否堵在第i个子前面,针对"车"和"帅"和"炮"
	if (P(i, (po + 1) % 2) != P(j, (po + 1) % 2)) return 0;
	int ii = P(i, po) - P(0, po), jj = P(j, po) - P(0, po);
	if (ii > 0 && jj > 0 && ii > jj) return 1;
	if (ii < 0 && jj < 0 && ii < jj) return 1;
	return 0;
}
inline bool f2(int i) {//判断第i个子是不是在"将"周围
	if (P(i, 0) == P(0, 0) && abs(P(i, 1) - P(0, 1)) == 1) return 1;
	if (P(i, 1) == P(0, 1) && abs(P(i, 0) - P(0, 0)) == 1) return 1;
	return 0;
}
bool f3(int i, int xx, int yy) {//判断"马"是否可以到达"将"周围
	if ((abs(xx) == 2 && abs(yy) == 1) || (abs(xx) == 1 && abs(yy) == 2)) {
		for (int j = 0;j <= N;++j) {
			if (P(j, 0) == P(i, 0) - int(xx / 2) && P(j, 1) == P(i, 1) - int(yy / 2)) return 0;
			//cerr <<"H:"<<i<<' '<<j<<'\t'<< P(j, 0) << ' ' << P(i, 0) - int(xx / 2) << '\t' << P(j, 0) << ' ' << P(i, 1) - int(yy / 1) << '\n';//-------------------
		}
		return 1;
	}
	return 0;
}
void GR(int i, bool po) {//"将"和"车"的函数
	if (P(i, (po + 1) % 2)>P(0, (po + 1) % 2) + 1 || P(i, (po + 1) % 2) < P(0, (po + 1) % 2) - 1) return;
	int j = 1;
	for (;j <= N&&!f1(i, j, po);++j);
	if (j > N) {
		if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) - 1) { if (!f2(i)) A[(po + 1) % 2] = 1; }
		else if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) + 1) { if (!f2(i))A[(po + 1) % 2 + 2] = 1; }
		else if (f2(i)) P(i, po) - P(0, po) > 0 ? A[po] = 1 : A[po + 2] = 1;
		else A[po] = A[po + 2] = 1;
	}
}
void H(int i) {//"马"的函数
	if (f2(i)) return;
	if (!A[0] && f3(i, P(i, 0) - (P(0, 0) - 1), P(i, 1) - P(0, 1))) A[0] = 1;
	if (!A[1] && f3(i, P(i, 0) - P(0, 0), P(i, 1) - (P(0, 1) - 1))) A[1] = 1;
	if (!A[2] && f3(i, P(i, 0) - (P(0, 0) + 1), P(i, 1) - P(0, 1))) A[2] = 1;
	if (!A[3] && f3(i, P(i, 0) - P(0, 0), P(i, 1) - (P(0, 1) + 1))) A[3] = 1;
}
void C(int i, bool po) {//"炮"的函数
	if (f2(i) || P(i, (po + 1) % 2) > P(0, (po + 1) % 2) + 1 || P(i, (po + 1) % 2) < P(0, (po + 1) % 2) - 1) return;
	int flag = 0;
	for (int j = 1;j <= N;++j) if (f1(i, j, po)) ++flag;
	if (flag == 1) {
		if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) - 1) A[(po + 1) % 2] = 1;
		else if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) + 1) A[(po + 1) % 2 + 2] = 1;
		else {
			int j = 1;
			for (;j <= N;++j) if (f1(i, j, po) && f2(j)) break;
			if (j <= N) P(i, po) - P(0, po) > 0 ? A[po] = 1 : A[po + 2] = 1;
			else A[po] = A[po + 2] = 1;
		}
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	while ((cin >> N >> P(0, 0) >> P(0, 1)) && N && P(0, 0) && P(0, 1)) {
		for (int i = 1;i <= N;++i)
			cin >> Pi[i].name >> P(i, 0) >> P(i, 1);
		A[0] = (P(0, 0) == 1 ? 1 : 0);
		A[1] = (P(0, 1) == 4 ? 1 : 0);
		A[2] = (P(0, 0) == 3 ? 1 : 0);
		A[3] = (P(0, 1) == 6 ? 1 : 0);
		//cerr << "A:" << A[0] << '\t' << A[1] << '\t' << A[2] << '\t' << A[3] << "\n";//--------
		for (int i = 1;i <= N;++i) {
			if (Pi[i].name == 'G') GR(i, 0);
			else if (Pi[i].name == 'R') GR(i, 0), GR(i, 1);
			else if (Pi[i].name == 'H') H(i);
			else C(i, 0), C(i, 1);
		}
		int i;
		//cerr << "A:" << A[0] << '\t' << A[1] << '\t' << A[2] << '\t' << A[3] << "\n";//--------
		for (i = 0;i < 4 && A[i];++i);
		cout << (i < 4 ? "NO" : "YES") << '\n';
	}
	return 0;
}

分析： 看着挺烦的，以为会调试很久，有那么多情况，感觉还不好找出错的点。结果两遍就AC了，喜出望外~ 我的思路是，判断每个子有没有把“将”周围堵住，对棋子大循环。同时我没有定义9*10的大棋盘。（现在想想定义了个棋盘好像简单好多。甚至可以打表查看哪里红子可以到达。或许我太过在意空间的占用了） A[4]的0上 1左 2下 3右是有顺序要求的，这样定义可以方便地和po对应起来。 车炮帅的攻击范围都是直线，所以定义的函数只针对其中一个方向，而G只能是向x轴方向出击，所以是只使用向x轴（po=0）方向的函数，而车和炮要使用两次函数。这三者有两种情况将军，第一是指向“将”旁边，使“将”无法向旁边行走。另一种是直接指向“将”，使之只能往旁边走不能在车炮指向的方向行走。三者都得考虑被堵住看不见“将”的情况。 不过这题有个小bug，就是将和帅面对面的情况，将可以直接飞过去翻盘赢了，无需躲闪。但是题目好像没有考虑这种情况，应该是规避了这类输入数据。我也是点击“Submit”时突然想起来这个情况没写。。。不过竟然AC了，那就算了。。。 还有就是车和炮直接在将旁边的情况，将可以吃掉它们消除威胁（当然前提是没有别人可以吃这个位置）。这个情况下，比如红车在（1，6），黑将在（1，5），那么黑将可以向右吃掉它，但是不能向左，因为向左进入（1，4）后车依然可以吃“将”。这是比较特殊的。 还有就是这一段： 

1
2
3
//在GR(...)函数的最后几行
if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) - 1) { if (!f2(i)) A[(po + 1) % 2] = 1; }
else if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) + 1) { if (!f2(i))A[(po + 1) % 2 + 2] = 1; }
本来我写的是

1
2
if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) - 1) A[(po + 1) % 2] = 1;
else if (P(i, (po + 1) % 2) == P(0, (po + 1) % 2) + 1) A[(po + 1) % 2 + 2] = 1;

没有后面的if。结果出现的问题就是当比如车在（1，6），将在（1，5）时，会判定为在针对x轴方向时，（1，6）（即将右侧，即A[3]）是将不可以走的。 还有炮的函数C，对于该函数最后几行，

1
2
3
4
5
6
else {
            int j = 1;
            for (;j <= N;++j) if (f1(i, j, po) && f2(j)) break;
            if (j <= N) P(i, po) - P(0, po) > 0 ? A[po] = 1 : A[po + 2] = 1;
            else A[po] = A[po + 2] = 1;
        }

意思是，如果炮架子刚好在将前面，那么炮只能攻击将的后面（即“将”不能后移），将前面即跑架子所在那个点打不到。 马的函数竟然算是最简单的了。。判断够不够得到将旁边的点，已及马有没有蹩脚即可。

附：uDebug上看到的测试数据： 2 1 4 G 10 5 R 6 4

3 1 5 H 4 5 G 10 5 C 7 5

2 1 5 R 4 4 G 10 5

3 1 5 G 10 4 R 5 5 H 3 7

4 1 5 G 10 4 C 6 5 H 5 5 R 1 1

5 1 5 G 10 4 C 6 5 H 5 5 H 4 5 R 1 1

3 1 5 G 10 4 C 2 7 H 3 7

3 1 5 G 10 4 R 5 5 R 1 6

4 1 5 G 10 4 R 5 5 R 1 6 H 3 7

0 0 0