今天面试了一个妹子，穿着超短裙来的，我把她pass了，但是加了她的联系方式，相约她出来吃饭。

程序员日常就像猫和老鼠游戏，谁没在 Bug 面前当过被追的“Jerry”呢？

说正经的，这道“猫和老鼠”题，题意大概是：在一个图中，猫和老鼠轮流走格子，鼠想要逃到洞里，猫想要抓住鼠，问到底是鼠赢、猫赢，还是平局。

熟悉 LeetCode 的人一看就知道，这是经典的 图论博弈题，可以建模成状态转移问题，关键是：多状态 + 轮流行动 + 胜负判断，直接暴力DFS可不行，必须得记忆化+状态判定，甚至用BFS来反推胜负状态。

Java代码思路如下：

publicclassCatMouseGame {
staticfinalintDRAW=0, MOUSE_WIN = 1, CAT_WIN = 2;

publicintcatMouseGame(int[][] graph) {
intn= graph.length;
int[][][] dp = newint[n][n][2 * n];

for (intt=0; t < 2 * n; t++) {
for (intx=0; x < n; x++) {
for (inty=0; y < n; y++) {
                    dp[x][y][t] = -1;
                }
            }
        }

return dfs(graph, dp, 1, 2, 0);
    }

privateintdfs(int[][] graph, int mouse, int cat, int turns, int[][][] dp) {
if (turns == 2 * graph.length) return DRAW;
if (mouse == 0) return MOUSE_WIN;
if (mouse == cat) return CAT_WIN;
if (dp[mouse][cat][turns] != -1) return dp[mouse][cat][turns];

booleanmouseTurn= (turns % 2 == 0);
intresult= mouseTurn ? CAT_WIN : MOUSE_WIN;
intcur= mouseTurn ? mouse : cat;

for (int next : graph[cur]) {
if (!mouseTurn && next == 0) continue; // 猫不能进洞

intnextMouse= mouseTurn ? next : mouse;
intnextCat= mouseTurn ? cat : next;
intnextResult= dfs(graph, nextMouse, nextCat, turns + 1, dp);

if (mouseTurn && nextResult == MOUSE_WIN) {
return dp[mouse][cat][turns] = MOUSE_WIN;
            }
if (!mouseTurn && nextResult == CAT_WIN) {
return dp[mouse][cat][turns] = CAT_WIN;
            }

if (mouseTurn && nextResult == DRAW) result = DRAW;
if (!mouseTurn && nextResult == DRAW) result = DRAW;
        }

return dp[mouse][cat][turns] = result;
    }
}

这玩意乍一看有点吓人，其实和面试官的套路一个样：绕，但不无解 🧐

关键在于理解三种状态：

• • 鼠赢：mouse 到了洞。
• • 猫赢：mouse 和 cat 重合。
• • 平局：走了两倍节点数还没分出胜负，懒得等了。

鼠和猫轮流走，鼠先动。猫不能走到0号点（即洞）。这么一说，是不是突然变得像小时候玩的“谁先被逼进死角谁就输”的游戏了？不过程序员玩的是状态压缩，不是感情 🙃

那为啥不能暴力DFS呢？想想每个状态 (mouse, cat, turn) 有 n*n*2n 种组合，爆掉内存是迟早的事，必须靠记忆化来“反复横跳”，把已经搜过的状态直接剪掉。

顺便一提，有些人用BFS从终点往回推，我试过，但代码结构上容易绕出宇宙，不如DFS清晰。不过你要面试刷 LeetCode 的话，推荐两个都写，毕竟面试官看你脸色说话，灵活就完事了。

🐭🐱 这题的本质，就是模拟两个人在博弈，每个人都想走到对自己最有利的地方，这时候就考验“你站在对手的角度想问题”的能力了。

要我说，这题最像我们写代码时和产品经理斗智斗勇的过程：我出一个功能，他改一条需求，我绕过去，他又补一脚，最后你以为赢了，其实是平局——代码上线当天全崩 😭

再说回代码，真正有意思的是这个问题背后的“状态空间压缩”和“轮流动作”的建模逻辑，不仅考察你写逻辑的能力，还考察你对图、搜索、博弈的理解程度，想在算法面试里出彩，这题必须掌握。

还有最后一点建议：如果你看到这类题还用 System.out.println 打日志调试，那你就别学猫抓老鼠了，建议直接开开心心看 Tom 和 Jerry 动画片，至少剧情简单、没递归栈溢出 😅