UVa 10358 Matrix

题目描述

在一个 $8\times 8$ 的棋盘上，你和两个特工进行追逐博弈。棋盘有三种方格：地板（.）、墙壁（#）和电话（P）。你的起始位置用 M 表示，两个特工的起始位置用 A 表示。你和特工每回合可以移动到相邻的四个方向或停留在原地，但不能移动到墙壁方格。移动规则允许棋子移动到已被其他棋子占据的方格。

游戏过程交替进行：你先移动，然后两个特工同时移动，如此循环。如果某回合结束时你位于一个未被特工占据的电话方格，则你成功逃脱。如果某回合结束时你与任意特工位于同一方格，则你被消灭。如果游戏无限进行下去，则视为你被困在矩阵中。

你的任务是：给定一个棋盘布局，判断你是能够必定逃脱，还是必定被消灭，还是可能被困。

输入格式

第一行是一个正整数 $n$，表示测试场景的数量。接下来是 $n$ 个场景，每个场景由 $8$ 行组成，每行 $8$ 个字符，字符集为 {'.', '#', 'P', 'A', 'M'}。其中：

• '.' 表示地板方格
• '#' 表示墙壁方格
• 'P' 表示电话方格
• 'A' 表示特工起始位置（每个场景恰好有两个）
• 'M' 表示你的起始位置（每个场景恰好一个）

初始所有棋子的位置都是地板方格。每个场景结束后有一个空行（包括最后一个场景之后）。

输出格式

对于每个场景，输出一行：

• 如果你可以必定逃脱，输出 You can escape.
• 如果特工可以必定消灭你，输出 You are eliminated.
• 否则输出 You are trapped in the Matrix.

样例

输入

3
#####.##
#####.##
#####.##
AA.M…P
#####.##
#####.##
#####.##
#####.##

########
#..P…#
#.####.#
#P#M.#P#
#.####.#
#..P…#
#A….A#
########

########
#…A.P#
#.######
#..M…#
#.####.#
..####..
#….A.#
########

输出

You can escape.
You are trapped in the Matrix.
You are eliminated.

题目分析

本题是一个双人零和博弈问题，棋盘大小为 $8\times 8$，状态空间有限。你的目标是到达任意一个未被特工占据的电话方格，特工的目标是与你重合。

关键特性：

• 你和特工的移动速度相同（每回合均可移动一格或停留）
• 两个特工协同作战，且知道你的所有位置信息（完美信息博弈）
• 棋子可以移动到被其他棋子占据的方格，移动后立即判定胜负

由于存在 “停留” 动作（即选择不移动），游戏可能陷入无限循环。例如，双方都不移动时，状态完全相同，博弈不会终止。因此，直接进行深度优先搜索（$\text{DFS}$）会导致无限递归。

这类问题的标准解法是使用逆向博弈搜索（类似解决“安全位置”问题），从终局状态反向标记每个状态是“必胜”（你可以强制胜利）、“必败”（特工可以强制抓住你）还是“平局”（困住）。由于棋盘有墙且至少一半是墙壁，有效状态数有限，可以采用带深度限制的 $\text{DFS}$ 或 $\text{BFS}$ 求解。

解题思路

状态定义

定义状态为：

• 你的位置：$(mx,my)$，其中 $0\le mx,my\le 7$
• 特工 $1$ 的位置：$(a1x,a1y)$
• 特工 $2$ 的位置：$(a2x,a2y)$
• 当前轮到谁移动：$turn$，$0$ 表示你的回合，$1$ 表示特工回合

总状态数为 $8\times 8\times 8\times 8\times 8\times 8\times 2=524,288$，完全可存储。

胜负判定规则

在任意状态：

• 如果 $isPhone(mx,my)$ 为真，且你不被特工抓住，则你立即获胜（逃脱）。
• 如果 $caught(mx,my,a1x,a1y,a2x,a2y)$ 为真，则你立即失败（被消灭）。

博弈转移

• 你的回合（$turn=0$）：你选择移动到某个相邻或停留的位置（共 $5$ 种可能，需检查是否合法）。如果存在一个移动能使你进入必胜状态，则当前状态为必胜。如果所有移动都进入必败状态，则当前为必败。否则为平局（困住）。
• 特工回合（$turn=1$）：两个特工同时选择各自的移动（各 $5$ 种可能，共 $25$ 种组合）。特工会选择对你最不利的移动：如果存在一个移动组合能使你进入必败状态，则当前为必败。如果所有移动组合都使你进入必胜状态，则当前为必胜。否则为平局。

防止无限递归

由于双方都可以选择“停留”，状态图中可能存在环。直接 $\text{DFS}$ 会导致栈溢出。解决方案：

• 引入深度限制：设定最大搜索深度（如 $40$ 步），超过深度则判定为平局。经验表明，在 $8\times 8$ 且有至少一半墙壁的棋盘上，有效博弈通常不会超过 $40$ 回合。
• 或者使用逆向 $\text{BFS}$：从所有终局状态反向标记，利用拓扑序求解。但实现较复杂，深度限制法更简洁且足以通过本题。

复杂度分析

• 状态数：$O(8^6\times 2)=O(524,288)$
• 每个状态转移：你的回合 $O(5)$，特工回合 $O(25)$
• 总计算量：约 $524,288\times 25\approx 13$ 百万次状态转移，在 $\text{C++}$ 中完全可行
• 空间复杂度：$O(8^6\times 2\times \text{MAX\_DEPTH})$，当深度限制为 $100$ 时约 $50\text{MB}$，可接受

实现细节

代码实现

// Matrix
// UVa ID: 10358
// Verdict: Accepted
// Submission Date: 2026-06-13
// UVa Run Time: 0.590s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int dx[] = {0, 1, –1, 0, 0}, dy[] = {0, 0, 0, 1, –1};

int n;
vector<string> board(8);
int dp[8][8][8][8][8][8][2][100];

bool isWall(int x, int y) {
if (x < 0 || x >= 8 || y < 0 || y >= 8) return true;
return board[x][y] == '#';
}

bool isPhone(int x, int y) {
if (x < 0 || x >= 8 || y < 0 || y >= 8) return false;
return board[x][y] == 'P';
}

bool canMove(int x, int y, int nx, int ny) {
if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) return false;
if (isWall(nx, ny)) return false;
return true;
}

bool caught(int mx, int my, int a1x, int a1y, int a2x, int a2y) {
return (mx == a1x && my == a1y) || (mx == a2x && my == a2y);
}

bool canEscape(int mx, int my, int a1x, int a1y, int a2x, int a2y) {
return isPhone(mx, my) && !caught(mx, my, a1x, a1y, a2x, a2y);
}

int dfs(int mx, int my, int a1x, int a1y, int a2x, int a2y, int turn, int depth) {
if (depth > 40) return 0;

if (dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] != –1)
return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth];

if (canEscape(mx, my, a1x, a1y, a2x, a2y))
return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 1;
if (caught(mx, my, a1x, a1y, a2x, a2y))
return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 2;

if (turn == 0) {
bool canWin = false, allLose = true;
for (int d = 0; d < 5; d++) {
int nmx = mx + dx[d], nmy = my + dy[d];
if (!canMove(mx, my, nmx, nmy)) continue;
int r = dfs(nmx, nmy, a1x, a1y, a2x, a2y, 1, depth + 1);
if (r == 1) canWin = true;
if (r != 2) allLose = false;
}
if (canWin) return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 1;
if (allLose) return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 2;
return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 0;
}
else {
bool canCatch = false, allEscape = true;
for (int d1 = 0; d1 < 5; d1++) {
int na1x = a1x + dx[d1], na1y = a1y + dy[d1];
if (!canMove(a1x, a1y, na1x, na1y)) continue;
for (int d2 = 0; d2 < 5; d2++) {
int na2x = a2x + dx[d2], na2y = a2y + dy[d2];
if (!canMove(a2x, a2y, na2x, na2y)) continue;
int r = dfs(mx, my, na1x, na1y, na2x, na2y, 0, depth + 1);
if (r == 2) canCatch = true;
if (r != 1) allEscape = false;
}
}
if (canCatch) return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 2;
if (allEscape) return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 1;
return dp[mx][my][a1x][a1y][a2x][a2y][turn][depth] = 0;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

cin >> n;
cin.ignore();

for (int t = 0; t < n; t++) {
for (int i = 0; i < 8; i++) getline(cin, board[i]);
string line;
getline(cin, line);

int mx, my, a1x = –1, a1y, a2x, a2y, agentCnt = 0;
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
if (board[i][j] == 'M') mx = i, my = j;
else if (board[i][j] == 'A')
if (agentCnt++ == 0) a1x = i, a1y = j;
else a2x = i, a2y = j;

memset(dp, –1, sizeof(dp));
int r = dfs(mx, my, a1x, a1y, a2x, a2y, 0, 0);

if (r == 1) cout << "You can escape.\\n";
else if (r == 2) cout << "You are eliminated.\\n";
else cout << "You are trapped in the Matrix.\\n";
}

return 0;
}

总结

本题的核心难点在于处理博弈中的循环状态。通过引入深度限制，我们成功避免了无限递归，同时保证了在有限深度内能够判定胜负。

关键技巧：

• 使用带记忆化的深度优先搜索（$\text{DFS}$ with memoization）对博弈状态进行标记。
• 对于双人零和博弈，轮流定义必胜/必败状态的转移规则。
• 当存在停留动作时，必须处理循环，深度限制是一种简单有效的工程解法。

本题也适合用逆向 $\text{BFS}$ 求解，但实现稍复杂。深度限制法在本问题约束下（棋盘小、墙多）足够高效且代码简洁，是一种实用的折中方案。