2014
11-05

# Queen’s Case

A small country called Maltius was governed by a queen. The queen was known as an oppressive ruler.People in the country suffered from heavy taxes and forced labor. So some young people decided to form a revolutionary army and fight against the queen. Now, they besieged the palace and have just rushed into the entrance.

Your task is to write a program to determine whether the queen can escape or will be caught by the army.

Here is detailed description.
●  The palace can be considered as grid squares.
●  The queen and the army move alternately. The queen moves first.
●  At each of their turns, they either move to an adjacent cell or stay at the same cell.
●  Each of them must follow the optimal strategy.
●  If the queen and the army are at the same cell, the queen will be caught by the army immediately.
●  If the queen is at any of exit cells alone after the army’s turn, the queen can escape from the army.
●  There may be cases in which the queen cannot escape but won’t be caught by the army forever,
under their optimal strategies.

The input describes a map of the palace. The first line of the input contains two integers W (1 <= W <= 30) and H (1 <=H <= 30), which indicate the width and height of the palace. The following H lines, each of which contains W characters, denote the map of the palace. “Q” indicates the queen,“A” the army,“E” an exit,“#” a wall and “.” a floor.

The map contains exactly one “Q”, exactly one “A” and at least one “E”. You can assume both the queen and the army can reach all the exits

The input describes a map of the palace. The first line of the input contains two integers W (1 <= W <= 30) and H (1 <=H <= 30), which indicate the width and height of the palace. The following H lines, each of which contains W characters, denote the map of the palace. “Q” indicates the queen,“A” the army,“E” an exit,“#” a wall and “.” a floor.

The map contains exactly one “Q”, exactly one “A” and at least one “E”. You can assume both the queen and the army can reach all the exits

2 2
QE
EA
3 1
QAE
3 1
AQE
5 5
..E..
.###.
A###Q
.###.
..E..
5 1
A.E.Q
5 5
A....
####.
..E..
.####
....Q

Queen can not escape and Army can not catch Queen.
Army can catch Queen.
Queen can escape.
Queen can not escape and Army can not catch Queen.
Army can catch Queen.
Army can catch Queen.

HintOn the first sample input, the queen can move to exit cells, but either way the queen will be caught at the next army’s turn. So the optimal
strategy for the queen is staying at the same cell. Then the army can move to exit cells as well, but again either way the army will miss the queen from
the other exit. So the optimal strategy for the army is also staying at the same cell. Thus the queen cannot escape but won’t be caught. 

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define MP(a, b) make_pair(a, b)
#define FOREACH(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)

const int MAX_R = 30 + 1;
//const int dir[5][2] = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int dir[5][2] = {{0, 0}, {0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int R, C;
int dp[MAX_R][MAX_R][MAX_R][MAX_R], vis[MAX_R][MAX_R];
char mat[MAX_R][MAX_R];

int valid(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C && mat[r][c] != '#';
}

int searchQ(int qr, int qc, int ar, int ac) {
int &ret = dp[qr][qc][ar][ac];
if (ret != -1)
return ret;
if (qr == ar && qc == ac)
return ret = 0;
if (mat[qr][qc] == 'E')
return ret = 1;
ret = 0;
int nqr, nqc, nar, nac;
for (int i = 1; i < 5 && !ret; i++) {
nqr = qr + dir[i][0];
nqc = qc + dir[i][1];
if (!valid(nqr, nqc) || vis[nqr][nqc]) continue;
if (nqr == ar && nqc == ac)
continue;
vis[nqr][nqc] = 1;
int win = 1;
for (int j = 0; j < 5 && win; j++) {
nar = ar + dir[j][0];
nac = ac + dir[j][1];
if (!valid(nar, nac)) continue;
win &= searchQ(nqr, nqc, nar, nac);
}
vis[nqr][nqc] = 0;
ret |= win;
}
return ret;
}

int searchA(int qr, int qc, int ar, int ac) {
int &ret = dp[qr][qc][ar][ac];
if (ret != -1)
return ret;
if (qr == ar && qc == ac)
return ret = 1;
if (mat[qr][qc] == 'E')
return ret = 0;
ret = 0;
int nqr, nqc, nar, nac;
for (int i = 1; i < 5 && !ret; i++) {
nar = ar + dir[i][0];
nac = ac + dir[i][1];
if (!valid(nar, nac) || vis[nar][nac]) continue;
vis[nar][nac] = 1;
int win = 1;
for (int j = 0; j < 5 && win; j++) {
nqr = qr + dir[j][0];
nqc = qc + dir[j][1];
if (!valid(nqr, nqc)) continue;
if (nqr == ar && nqc == ac)
continue;
win &= searchA(nqr, nqc, nar, nac);
}
vis[nar][nac] = 0;
ret |= win;
}
return ret;
}

int main() {
while (~scanf("%d %d", &C, &R)) {
int sQr, sQc, sAr, sAc;
for (int r = 0; r < R; r++) {
scanf("%s", mat[r]);
for (int c = 0; c < C; c++) {
if (mat[r][c] == 'Q') sQr = r, sQc = c;
if (mat[r][c] == 'A') sAr = r, sAc = c;
}
}

memset(dp, -1, sizeof(dp));
memset(vis, 0, sizeof(vis));
vis[sQr][sQc] = 1;
int escape = searchQ(sQr, sQc, sAr, sAc);
if (escape) puts("Queen can escape.");
else {
memset(dp, -1, sizeof(dp));
memset(vis, 0, sizeof(vis));
vis[sAr][sAc] = 1;
int cath = searchA(sQr, sQc, sAr, sAc);
if (!cath) puts("Queen can not escape and Army can not catch Queen.");
else puts("Army can catch Queen.");
}
}
return 0;
}

1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。