書上具體所有題目：http://pan.baidu.com/s/1hssH0KO
代碼：（Accepted，0 ms）
#include<iostream>
#include<cmath>
#define P(x,y) Pi[x].position[y]
using namespace std;
int N;
bool A[
4];
struct piece {
char name;
int position[
2];
}Pi[
10];
inline bool f1(
int i,
int j,
bool po) {
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) {
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;}
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()
{
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);
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;
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）后車依然可以吃“將”。這是比較特殊的。
還有就是這一段：
//在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; }
本來我寫的是
if (P(
i, (po +
1)
else if (P(
i, (po +
1)
沒有后面的if。結果出現的問題就是當比如車在（1，6），將在（1，5）時，會判定為在針對x軸方向時，（1，6）（即將右側，即A[3]）是將不可以走的。
還有炮的函數C，對于該函數最后幾行，
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
轉載于:https://www.cnblogs.com/xienaoban/p/6798106.html
總結
以上是生活随笔為你收集整理的[刷题]算法竞赛入门经典(第2版) 4-1/UVa1589 - Xiangqi的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
