拓扑排序:求解《913. 猫和老鼠》和《1728. 猫和老鼠 II》

2022-05-11 09:02:04
拓扑排序,求解《913. 猫和老鼠》和《1728. 猫和老鼠 II》

例题

913. 猫和老鼠

两位玩家分别扮演猫和老鼠,在一张 无向 图上进行游戏,两人轮流行动。
图的形式是:graph[a] 是一个列表,由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始,第一个出发;猫从节点 2 开始,第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中,他们 必须 沿着图中与所在当前位置连通的一条边移动。例如,如果老鼠在节点 1 ,那么它必须移动到 graph[1] 中的任一节点。
此外,猫无法移动到洞中(节点 0)。
然后,游戏在出现以下三种情形之一时结束:
如果猫和老鼠出现在同一个节点,猫获胜。
如果老鼠到达洞中,老鼠获胜。
如果某一位置重复出现(即,玩家的位置和移动顺序都与上一次行动相同),游戏平局。
给你一张图 graph ,并假设两位玩家都都以最佳状态参与游戏:
如果老鼠获胜,则返回 1;
如果猫获胜,则返回 2;
如果平局,则返回 0 。

示例

913. 猫和老鼠拓扑无向图
输入: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
};

代码
邻接表:深度优先搜索、广度优先搜索和拓扑排序求解最小高度树
用邻接表数据结构,广度优先搜索、深度优先搜索(递归和迭代)、拓扑排序求解最小高度树。