拓扑排序，求解《913. 猫和老鼠》和《1728. 猫和老鼠 II》 答案
答案
例题
913. 猫和老鼠
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。示例
输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
输出：0
答案
拓扑排序-1
var catMouseGame = function(graph) {
const MOUSE_TURN = 0
const CAT_TURN = 1
const MOUSE_WIN = 1
const CAT_WIN = 2
const DRAW = 0
const n = graph.length
const degrees = Array.from({length: n}, _ => Array.from({length: n}, _ => new Uint8Array(2)))
const results = Array.from({length: n}, _ => Array.from({length: n}, _ => new Uint8Array(2)))
// 入度
for (let i = 0; i < n; i++) {
for (let j = 1; j < n; j++) {
degrees[i][j][MOUSE_TURN] = graph[i].length
degrees[i][j][CAT_TURN] = graph[j].length
}
}
for (let j = 0, len = graph[0].length; j < len; j++) {
for (let i = 0; i < n; i++) {
degrees[i][graph[0][j]][CAT_TURN]--
}
}
const q = []
// 结果
for (let j = 1; j < n; j++) {
results[0][j][MOUSE_TURN] = MOUSE_WIN
results[0][j][CAT_TURN] = MOUSE_WIN
q.push([0, j, MOUSE_TURN], [0, j, CAT_TURN])
results[j][j][MOUSE_TURN] = CAT_WIN
results[j][j][CAT_TURN] = CAT_WIN
q.push([j, j, MOUSE_TURN], [j, j, CAT_TURN])
}
// 获取上一状态列表
function getPrevStates (curState) {
const prevStates = []
const [curMouse, curCat, curTurn] = curState
if (curTurn === MOUSE_TURN) {
for (const cat of graph[curCat]) {
if (cat !== 0) prevStates.push([curMouse, cat, CAT_TURN])
}
} else {
for (const mouse of graph[curMouse]) {
if (mouse !== 0) prevStates.push([mouse, curCat, MOUSE_TURN])
}
}
return prevStates
}
// 拓扑排序
while (q.length) {
const curState = q.shift()
const [curMouse, curCat, curTurn] = curState
const curResult = results[curMouse][curCat][curTurn]
const prevStates = getPrevStates(curState)
for (const prevState of prevStates) {
const [prevMouse, prevCat, prevTurn] = prevState
if (results[prevMouse][prevCat][prevTurn] === DRAW) {
if (
curResult === MOUSE_WIN && prevTurn === MOUSE_TURN ||
curResult === CAT_WIN && prevTurn === CAT_TURN
) {
results[prevMouse][prevCat][prevTurn] = curResult
q.push(prevState)
} else {
degrees[prevMouse][prevCat][prevTurn]--
if (degrees[prevMouse][prevCat][prevTurn] === 0) {
results[prevMouse][prevCat][prevTurn] = prevTurn === MOUSE_TURN ? CAT_WIN : MOUSE_WIN
q.push(prevState)
}
}
}
}
}
return results[1][2][MOUSE_TURN]
};const (
mouseTurn = 0
catTurn = 1
mouseWin = 1
catWin = 2
draw = 0
)
type state struct {
mouse,
cat,
turn int
}
func catMouseGame(graph [][]int) int {
n := len(graph)
degrees := make([][][2]int, n)
results := make([][][2]int, n)
// 构造数组
for i := range graph {
degrees[i] = make([][2]int, n)
results[i] = make([][2]int, n)
}
// 入度
for i, row := range graph { // mouse
for j := 1; j < n; j++ { // cat
degrees[i][j][mouseTurn] = len(row)
degrees[i][j][catTurn] = len(graph[j])
}
}
for _, j := range graph[0] { // cat 不能进洞
for i := 0; i < n; i++ {
degrees[i][j][catTurn]--
}
}
q := []state{}
// 结果：自底向上，逆推
for j := 1; j < n; j++ { // 老鼠到洞中 i = 0 或 猫抓住老鼠 i = j
results[0][j][catTurn] = mouseWin
results[0][j][mouseTurn] = mouseWin
q = append(q, state{0, j, catTurn}, state{0, j, mouseTurn})
results[j][j][catTurn] = catWin
results[j][j][mouseTurn] = catWin
q = append(q, state{j, j, catTurn}, state{j, j, mouseTurn})
}
getPrevStates := func(curState state) (prevStates []state) {
curMouse, curCat, curTurn := curState.mouse, curState.cat, curState.turn
if curTurn == mouseTurn { // 上一局 catTurn
for _, cat := range graph[curCat] {
if cat != 0 {
prevStates = append(prevStates, state{curMouse, cat, catTurn})
}
}
} else {
for _, mouse := range graph[curMouse] {
if mouse != 0 {
prevStates = append(prevStates, state{mouse, curCat, mouseTurn})
}
}
}
return
}
// 拓扑排序
for len(q) > 0 {
curState := q[0]
q = q[1:]
curMouse, curCat, curTurn := curState.mouse, curState.cat, curState.turn
curResult := results[curMouse][curCat][curTurn]
prevStates := getPrevStates(curState)
for _, prevState := range prevStates {
prevMouse, prevCat, prevTurn := prevState.mouse, prevState.cat, prevState.turn
if results[prevMouse][prevCat][prevTurn] == draw {
if curResult == mouseWin && prevTurn == mouseTurn || curResult == catWin && prevTurn == catTurn {
results[prevMouse][prevCat][prevTurn] = curResult
q = append(q, prevState)
} else {
degrees[prevMouse][prevCat][prevTurn]--
if degrees[prevMouse][prevCat][prevTurn] == 0 {// 必败
if prevTurn == mouseTurn {
results[prevMouse][prevCat][prevTurn] = catWin
} else {
results[prevMouse][prevCat][prevTurn] = mouseWin
}
q = append(q, prevState)
}
}
}
}
}
return results[1][2][mouseTurn]
}拓扑排序-2
class Solution {
private const MOUSE_TURN = 0;
private const CAT_TURN = 1;
private const MOUSE_WIN = 1;
private const CAT_WIN = 2;
private const DRAW = null;
function catMouseGame($graph) {
$n = count($graph);
$degrees = $results = [];
// 入度
foreach($graph as $i => $row) {
for ($j = 1; $j < $n; $j++) {
$degrees[$i][$j][self::MOUSE_TURN] = count($row);
$degrees[$i][$j][self::CAT_TURN] = count($graph[$j]);
}
}
foreach($graph[0] as $j) {
for ($i = 0; $i < $n; $i++) {
$degrees[$i][$j][self::CAT_TURN]--;
}
}
$q = [];
// 结果
for ($j = 1; $j < $n; $j++) {
$results[0][$j][self::MOUSE_TURN] = self::MOUSE_WIN;
$results[0][$j][self::CAT_TURN] = self::MOUSE_WIN;
array_push($q, [0, $j, self::MOUSE_TURN], [0, $j, self::CAT_TURN]);
$results[$j][$j][self::MOUSE_TURN] = self::CAT_WIN;
$results[$j][$j][self::CAT_TURN] = self::CAT_WIN;
array_push($q, [$j, $j, self::MOUSE_TURN], [$j, $j, self::CAT_TURN]);
}
// 拓扑排序
while (count($q) > 0) {
$curState = array_shift($q);
list($curMouse, $curCat, $curTurn) = $curState;
$curResult = $results[$curMouse][$curCat][$curTurn];
$prevStates = $this->getPrevStates($graph, $curState);
foreach ($prevStates as $prevState) {
list($prevMouse, $prevCat, $prevTurn) = $prevState;
if ($results[$prevMouse][$prevCat][$prevTurn] === self::DRAW) {
if (
$curResult === self::MOUSE_WIN && $prevTurn === self::MOUSE_TURN ||
$curResult === self::CAT_WIN && $prevTurn === self::CAT_TURN
) {
$results[$prevMouse][$prevCat][$prevTurn] = $curResult;
$q []= $prevState;
} else {
$degrees[$prevMouse][$prevCat][$prevTurn]--;
if ($degrees[$prevMouse][$prevCat][$prevTurn] === 0) {
$results[$prevMouse][$prevCat][$prevTurn] = $prevTurn === self::MOUSE_TURN ? self::CAT_WIN
: self::MOUSE_WIN;
$q []= $prevState;
}
}
}
}
}
$result = $results[1][2][self::MOUSE_TURN];
return $result === self::DRAW ? 0 : $result;
}
// 获取上一状态列表
function getPrevStates ($graph, $curStates) {
$prevStates = [];
list($curMouse, $curCat, $curTurn) = $curStates;
if ($curTurn === self::MOUSE_TURN) { // Cat Turn
foreach($graph[$curCat] as $cat) {
if ($cat !== 0) $prevStates []= [$curMouse, $cat, self::CAT_TURN];
}
} else {
foreach($graph[$curMouse] as $mouse) {
if ($mouse !== 0) $prevStates []= [$mouse, $curCat, self::MOUSE_TURN];
}
}
return $prevStates;
}
}function catMouseGame(graph: number[][]): number {
const MOUSE_TURN = 0
const CAT_TURN = 1
const MOUSE_WIN = 1
const CAT_WIN = 2
const DRAW = 0
const n = graph.length
const degrees = Array.from({length: n}, _ => Array.from({length: n}, _ => new Uint8Array(2)))
const results = Array.from({length: n}, _ => Array.from({length: n}, _ => new Uint8Array(2)))
// 入度
for (let i = 0; i < n; i++) {
for (let j = 1; j < n; j++) {
degrees[i][j][MOUSE_TURN] = graph[i].length
degrees[i][j][CAT_TURN] = graph[j].length
}
}
for (let j = 0, len = graph[0].length; j < len; j++) {
for (let i = 0; i < n; i++) {
degrees[i][graph[0][j]][CAT_TURN]--
}
}
const q = []
// 结果
for (let j = 1; j < n; j++) {
results[0][j][MOUSE_TURN] = MOUSE_WIN
results[0][j][CAT_TURN] = MOUSE_WIN
q.push([0, j, MOUSE_TURN], [0, j, CAT_TURN])
results[j][j][MOUSE_TURN] = CAT_WIN
results[j][j][CAT_TURN] = CAT_WIN
q.push([j, j, MOUSE_TURN], [j, j, CAT_TURN])
}
// 获取上一状态列表
function getPrevStates (curState) {
const prevStates = []
const [curMouse, curCat, curTurn] = curState
if (curTurn === MOUSE_TURN) {
for (const cat of graph[curCat]) {
if (cat !== 0) prevStates.push([curMouse, cat, CAT_TURN])
}
} else {
for (const mouse of graph[curMouse]) {
if (mouse !== 0) prevStates.push([mouse, curCat, MOUSE_TURN])
}
}
return prevStates
}
// 拓扑排序
while (q.length) {
const curState = q.shift()
const [curMouse, curCat, curTurn] = curState
const curResult = results[curMouse][curCat][curTurn]
const prevStates = getPrevStates(curState)
for (const prevState of prevStates) {
const [prevMouse, prevCat, prevTurn] = prevState
if (results[prevMouse][prevCat][prevTurn] === DRAW) {
if (
curResult === MOUSE_WIN && prevTurn === MOUSE_TURN ||
curResult === CAT_WIN && prevTurn === CAT_TURN
) {
results[prevMouse][prevCat][prevTurn] = curResult
q.push(prevState)
} else {
degrees[prevMouse][prevCat][prevTurn]--
if (degrees[prevMouse][prevCat][prevTurn] === 0) {
results[prevMouse][prevCat][prevTurn] = prevTurn === MOUSE_TURN ? CAT_WIN : MOUSE_WIN
q.push(prevState)
}
}
}
}
}
return results[1][2][MOUSE_TURN]
}; 1728. 猫和老鼠 II
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。
它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。
玩家由字符 'C' （代表猫）和 'M' （代表老鼠）表示。
地板由字符 '.' 表示，玩家可以通过这个格子。
墙用字符 '先移动 ，然后两名玩家轮流移动。
每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出 grid 。
catJump 和 mouseJump 是猫和老鼠分别跳一次能到达的最远距离，它们也可以跳小于最大距离的长度。
它们可以停留在原地。
老鼠可以跳跃过猫的位置。
游戏有 4 种方式会结束：
如果猫跟老鼠处在相同的位置，那么猫获胜。
如果猫先到达食物，那么猫获胜。
如果老鼠先到达食物，那么老鼠获胜。
如果老鼠不能在 1000 次操作以内到达食物，那么猫获胜。
给你 rows x cols 的矩阵 grid 和两个整数 catJump 和 mouseJump ，双方都采取最优策略，如果老鼠获胜，那么请你返回 true ，否则返回 false 。
答案
拓扑排序
var canMouseWin = function(grid, catJump, mouseJump) {
const MOUSE_TURN = 0;
const CAT_TURN = 1;
const MOUSE_WIN = 1;
const CAT_WIN = 2;
const DRAW = 0;
const MAX_MOVES = 1000;
const n = grid.length, m = grid[0].length, total = m * n
const getPos = (x, y) => x * m + y, getXY = (pos) => [pos / m | 0, pos % m]
const degrees = Array.from({length: total}, _ => Array.from({length: total}, _ => new Uint16Array(2)))
const results = Array.from({length: total}, _ => Array.from({length: total}, _ => Array.from({length: 2}, _=> new Uint16Array(2))))
const ds = [[-1, 0], [1, 0], [0, -1], [0, 1]]
const isWall = (x, y) => grid[x][y] === '
const isInRange = (x, y) => x >= 0 && x < n && y >= 0 && y < m
const getNext = (startX, startY, maxJump, cb) => {
for (const d of ds) {
for (let x = startX + d[0], y = startY + d[1], jump = 1; isInRange(x, y) && jump <= maxJump; x += d[0], y += d[1], jump++) {
if (isWall(x, y)) break
cb(getPos(x, y))
}
}
}
// 入度
for (let mouse = 0; mouse < total; mouse++) {
const [mouseX, mouseY] = getXY(mouse)
if (isWall(mouseX, mouseY)) continue
for (let cat = 0; cat < total; cat++) {
const [catX, catY] = getXY(cat)
if (isWall(catX, catY)) continue
degrees[mouse][cat][MOUSE_TURN]++
degrees[mouse][cat][CAT_TURN]++
getNext(mouseX, mouseY, mouseJump, nextMouse => degrees[nextMouse][cat][MOUSE_TURN]++)
getNext(catX, catY, catJump, nextCat => degrees[mouse][nextCat][CAT_TURN]++)
}
}
// 起点
let startCat = startMouse = startFood = 0
for (let x = 0; x < n; x++) {
for (let y = 0; y < m; y++) {
switch (grid[x][y]) {
case 'C':
startCat = getPos(x, y)
break
case 'M':
startMouse = getPos(x, y)
break
case 'F':
startFood = getPos(x, y)
break
}
}
}
const q = []
// 结果
for (let i = 0; i < total; i++) { // 猫与老鼠相同位置
const [x, y] = getXY(i)
if (isWall(x, y)) continue
results[i][i][MOUSE_TURN] = [CAT_WIN, 0]
results[i][i][CAT_TURN] = [CAT_WIN, 0]
q.push([i, i, MOUSE_TURN], [i, i, CAT_TURN])
}
for (let i = 0; i < total; i++) { // 猫先得到食物
const [x, y] = getXY(i)
if (isWall(x, y) || i === startFood) continue
results[i][startFood][MOUSE_TURN] = [CAT_WIN, 0]
results[i][startFood][CAT_TURN] = [CAT_WIN, 0]
q.push([i, startFood, MOUSE_TURN], [i, startFood, CAT_TURN])
}
for (let j = 0; j < total; j++) { // 老鼠先得到食物
const [x, y] = getXY(j)
if (isWall(x, y) || j === startFood) continue
results[startFood][j][MOUSE_TURN] = [MOUSE_WIN, 0]
results[startFood][j][CAT_TURN] = [MOUSE_WIN, 0]
q.push([startFood, j, MOUSE_TURN], [startFood, j, CAT_TURN])
}
// 获取上一状态列表
function getPrevStates (curState) {
const [curMouse, curCat, curTurn] = curState
const prevStates = []
const prevTurn = curTurn === MOUSE_TURN ? CAT_TURN : MOUSE_TURN
prevStates.push([curMouse, curCat, prevTurn])
if (curTurn === MOUSE_TURN) {
getNext(...getXY(curCat), catJump, nextCat => prevStates.push([curMouse ,nextCat, CAT_TURN]))
} else {
getNext(...getXY(curMouse), mouseJump, nextMouse => prevStates.push([nextMouse, curCat, MOUSE_TURN]))
}
return prevStates
}
// 拓扑排序
while (q.length) {
const curState = q.shift()
const [curMouse, curCat, curTurn] = curState
const [curResult, curMove] = results[curMouse][curCat][curTurn]
const prevStates = getPrevStates(curState)
for (const prevState of prevStates) {
const [prevMouse, prevCat, prevTurn] = prevState
if (results[prevMouse][prevCat][prevTurn][0] === DRAW) {
if (
curResult === CAT_WIN && prevTurn === CAT_TURN ||
curResult === MOUSE_WIN && prevTurn === MOUSE_TURN
) {
results[prevMouse][prevCat][prevTurn] = [curResult, curMove + 1]
q.push(prevState)
} else {
degrees[prevMouse][prevCat][prevTurn]--
if (degrees[prevMouse][prevCat][prevTurn] === 0) {
results[prevMouse][prevCat][prevTurn] = [prevTurn === MOUSE_TURN ? CAT_WIN : MOUSE_WIN, curMove + 1]
q.push(prevState)
}
}
}
}
}
return results[startMouse][startCat][MOUSE_TURN][0] === MOUSE_WIN && results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES
};