Language: C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
const int dx[] = { -1, 0, 0, 1 }, dy[] = { 0, -1, 1, 0 };
//[const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

int dp[2][33][33][33][33]; //turn, x_queen, y_queen, x_army, y_army
int h, w;
vs fld;

struct state
{
	int turn, qx, qy, ax, ay;
	state(int a, int b, int c, int d, int e) :turn(a), qx(b), qy(c), ax(d), ay(e) {};
};

void init()
{
	fld.clear(); fld.resize(h);
	MS(dp, 0);
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	while (cin >> w >> h, h)
	{
		init();
		REP(i, h) cin >> fld[i];
		pii army, queen;
		set<pii> exit;
		REP(i, h)REP(j, w)
		{
			if (fld[i][j] == '#') continue;
			if (fld[i][j] == 'Q') queen = pii(i, j);
			if (fld[i][j] == 'A') army = pii(i, j);
			if (fld[i][j] == 'E') exit.emplace(i, j);
			fld[i][j] = '.';
		}
		vector<state> updates;
		for (auto i : exit)REP(ax, h)REP(ay, w)
		{
			int qx = i.first, qy = i.second;
			dp[0][qx][qy][ax][ay] = 1;
			updates.push_back(state(0, qx, qy, ax, ay));
		}
		REP(i, h)REP(j, w)
		{
			if (fld[i][j] == '#') continue;
			dp[0][i][j][i][j] = -1;
			updates.push_back(state(0, i, j, i, j));
		}
		REP(i, 2)REP(qx, h)REP(qy, w)REP(ax, h)REP(ay, w) updates.push_back(state(i, qx, qy, ax, ay));
		while (!updates.empty())
		{
			vector<state> nexts;
			for (auto tmp : updates)
			{
				bool update = false;
				int i = tmp.turn, qx = tmp.qx, qy = tmp.qy, ax = tmp.ax, ay = tmp.ay;
				if (!valid(qx, qy, h, w) || !valid(ax, ay, h, w) || dp[i][qx][qy][ax][ay] != 0) continue;
				if (i == 0)
				{
					set<int> st;
					st.insert(dp[1][qx][qy][ax][ay]);
					REP(j, 4)
					{
						int nx = qx + dx[j], ny = qy + dy[j];
						if (!valid(nx, ny, h, w) || fld[nx][ny] == '#') continue;
						st.insert(dp[1][nx][ny][ax][ay]);
					}
					if (st.size() == 1 && *st.begin() == -1)
					{
						dp[0][qx][qy][ax][ay] = -1;
						update = true;
					}
					else if (st.count(1))
					{
						dp[0][qx][qy][ax][ay] = 1;
						update = true;
					}
				}
				else
				{
					set<int> st;
					st.insert(dp[0][qx][qy][ax][ay]);
					REP(j, 4)
					{
						int nx = ax + dx[j], ny = ay + dy[j];
						if (!valid(nx, ny, h, w) || fld[nx][ny] == '#') continue;
						st.insert(dp[0][qx][qy][nx][ny]);
					}
					if (st.size() == 1 && *st.begin() == 1)
					{
						dp[1][qx][qy][ax][ay] = 1;
						update = true;
					}
					else if (st.count(-1))
					{
						dp[1][qx][qy][ax][ay] = -1;
						update = true;
					}
				}
				if (update)
				{
					REP(i, 2)REP(j, 4)REP(k, 4)
					nexts.push_back(state(i, qx + dx[j], qy + dy[j], ax + dx[k], ay + dy[k]));
				}
			}
			sort(ALL(updates));
			updates.erase(unique(ALL(updates)), updates.end());
			updates = nexts;
		}
		

		int ans = dp[0][queen.first][queen.second][army.first][army.second];
		if (ans == 1) cout << "Queen can escape." << endl;
		else if (ans == 0) cout << "Queen can not escape and Army can not catch Queen." << endl;
		else cout << "Army can catch Queen." << endl;
	}

	return 0;
}

Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_equal_to_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<state*, std::vector<state> >; _Iterator2 = __gnu_cxx::__normal_iterator<state*, std::vector<state> >]':
/usr/include/c++/14/bits/stl_algo.h:869:20:   required from '_ForwardIterator std::__unique(_ForwardIterator, _ForwardIterator, _BinaryPredicate) [with _ForwardIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _BinaryPredicate = __gnu_cxx::__ops::_Iter_equal_to_iter]'
  869 |         if (!__binary_pred(__dest, __first))
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:900:27:   required from '_FIter std::unique(_FIter, _FIter) [with _FIter = __gnu_cxx::__normal_iterator<state*, vector<state> >]'
  900 |       return std::__unique(__first, __last,
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
  901 |                            __gnu_cxx::__ops::__iter_equal_to_iter());
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:128:24:   required from here
  128 |                         updates.erase(unique(ALL(updates)), updates.end());
      |                                       ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:117:23: error: no match for 'operator==' (operand types are 'state' and 'state')
  117 |       { return *__it1 == *__it2; }
      |                ~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:67:
/usr/include/c++/14/bits/stl_iterator.h:1208:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator==(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1208 |     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1208:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:117:23: note:   'state' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
  117 |       { return *__it1 == *__it2; }
      |                ~~~~~~~^~~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1216:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator==(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1216 |     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1216:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:117:23: note:   'state' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
  117 |       { return *__it1 == *__it2; }
      |                ~~~~~~~^~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<state*, std::vector<state> >; _Iterator2 = __gnu_cxx::__normal_iterator<state*, std::vector<state> >]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<state*, vector<state> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:127:8:   required from here
  127 |                         sort(ALL(updates));
      |                         ~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:45:23: error: no match for 'operator<' (operand types are 'state' and 'state')
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:45:23: note:   'state' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1249 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:45:23: note:   'state' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = state; _Iterator = __gnu_cxx::__normal_iterator<state*, std::vector<state> >]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<state*, vector<state> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4772:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<state*, vector<state> >]'
 4772 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:127:8:   required from here
  127 |                         sort(ALL(updates));
      |                         ~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:98:22: error: no match for 'operator<' (operand types are 'state' and 'state')
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1241 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1241:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/predefined_ops.h:98:22: note:   'state' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   98 |       { return __val < *__it; }
      |                ~~~~~~^~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1249:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __normal_iterator<_Iterator, _Contain