题目不描述：

解题报告：

博弈，也可以搜索，从最终态开始，建立dp[2][30][30][30][30]的数组

dp[0][i][j][x][y]表示女王走完后，女王在i，j位置，士兵在x，y位置时的胜负状况

0：不确定，1：士兵胜，-1女王胜。

dp[0][i][j][x][y]表示士兵走完后，女王在i，j位置，士兵在x，y位置时的胜负状况

自底向上迭代：

首先把女王最后一步的必胜态和必输态决定下来（程序while之前的处理部分）

然后轮流依次士兵-女王-士兵-女王。。。。。

直到状态不能在修改。

严格按照解题报告里的两句话：

(1)如果当前先手能到达对手的必输状态，那么当前状态就是必赢状态。
(2)如果当前先手能到达的状态都是对手的必赢状态，那么当前状态一定是必输态。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int r, c, ans[2][30][30][30][30], move[5][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};
char x[35][35];
bool judge(int a, int b)
{
    return (a >= 0 && a < r && b >= 0 && b < c && x[a][b] != '#');
}
int main()
{
    while(scanf("%d%d", &c, &r) != EOF)
    {
        memset(ans, 0, sizeof(ans));
        int a[2], q[2];
        for(int i = 0; i < r; i++)
        {
            scanf("%s", x[i]);
            for(int j = 0; j < c; j++)
            {
                if (x[i][j] == 'E')
                {
                    for(int k = 0; k < 5; k++)
                    {
                        int tmpa = i + move[k][0], tmpb = j + move[k][1];
                        if (judge(tmpa, tmpb))
                            ans[0][i][j][tmpa][tmpb] = 1;
                    }
                    for(int k = 0; k < r; k++)
                        for(int l = 0; l < c; l++)
                            if (ans[0][i][j][k][l] == 0)
                                ans[0][i][j][k][l] = -1;
                }
                else if (x[i][j] == 'A')
                    a[0] = i, a[1] = j;
                else if (x[i][j] == 'Q')
                    q[0] = i, q[1] = j;
                ans[0][i][j][i][j] = ans[1][i][j][i][j] = 1;
            }
        }
        for(int i = 0; i < r; i++)
            for(int j = 0; j < c; j++)
            {
                for(int k = 0; k < 5; k++)
                {
                    int tmpa = i + move[k][0], tmpb = j + move[k][1];
                    if (judge(tmpa, tmpb))
                        ans[0][i][j][tmpa][tmpb] = 1;
                }
            }
        int id = 1;
        bool flag = true;
        while(flag)
        {
            flag = false;
            for(int i = 0; i < r; i++)
                for(int j = 0; j < c; j++)
                    if (judge(i, j))
                    {
                        for(int k = 0; k < r; k++)
                            for(int l = 0; l < c; l++)
                                if (judge(k, l) && ans[id][i][j][k][l] == 0)
                                {
                                    if(id == 1)
                                    {
                                        bool ff = true;
                                        for(int kk = 0; kk < 5; kk++)
                                        {
                                            int tmpa = i + move[kk][0], tmpb = j + move[kk][1];
                                            if (judge(tmpa, tmpb))
                                            {
                                                if(ans[0][tmpa][tmpb][k][l] == -1)
                                                {
                                                    ans[1][i][j][k][l] = -1;
                                                    flag = true;
                                                    break;
                                                }
                                                else if (ans[0][tmpa][tmpb][k][l] == 0)
                                                    ff = false;
                                            }
                                        }
                                        if (ff && ans[id][i][j][k][l] == 0)
                                        {
                                            ans[id][i][j][k][l] = 1;
                                            flag = true;
                                        }
                                    }
                                    else
                                    {
                                        bool ff = true;
                                        for(int kk = 0; kk < 5; kk++)
                                        {
                                            int tmpa = k + move[kk][0], tmpb = l + move[kk][1];
                                            if (judge(tmpa, tmpb))
                                            {
                                                if(ans[1][i][j][tmpa][tmpb] == 1)
                                                {
                                                    ans[0][i][j][k][l] = 1;
                                                    flag = true;
                                                    break;
                                                }
                                                else if (ans[1][i][j][tmpa][tmpb] == 0)
                                                    ff = false;
                                            }
                                        }
                                        if (ff && ans[id][i][j][k][l] == 0)
                                        {
                                            ans[id][i][j][k][l] = -1;
                                            flag = true;
                                        }
                                    }
                                }
                    }
            if (ans[1][q[0]][q[1]][a[0]][a[1]] != 0) break;
            id = (id + 1) % 2;
        }
        if (ans[1][q[0]][q[1]][a[0]][a[1]] == 0)
            printf("Queen can not escape and Army can not catch Queen.\n");
        else if (ans[1][q[0]][q[1]][a[0]][a[1]] == 1)
            printf("Army can catch Queen.\n");
        else printf("Queen can escape.\n");
    }
    return 0;
}