913.猫和老鼠.md

913.猫和老鼠

/*
 * @lc app=leetcode.cn id=913 lang=typescript
 *
 * [913] 猫和老鼠
 */

// @lc code=start
function catMouseGame(graph: number[][]): number {}
// @lc code=end

解法 1: 模拟

function catMouseGame(graph: number[][]): number {
  const n = graph.length
  const cache: number[][][] = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => []))

  const dfs = (i: number, j: number, k: number): number => {
    if (k >= 2 * n) {
      return 0
    }

    if (cache[i][j][k] !== undefined) {
      return cache[i][j][k]
    }

    if (i === 0) {
      return 1
    }
    if (i === j) {
      return 2
    }

    if ((k & 1) === 0) {
      let res = 2
      for (const child of graph[i]) {
        let tmp = dfs(child, j, k + 1)
        if (tmp === 1) {
          res = tmp
          break
        } else if (tmp === 0) {
          res = tmp
        }
      }
      cache[i][j][k] = res
      return res
    } else {
      let res = 1
      for (const child of graph[j]) {
        if (child === 0) {
          continue
        }
        let tmp = dfs(i, child, k + 1)
        if (tmp === 2) {
          res = tmp
          break
        } else if (tmp === 0) {
          res = tmp
        }
      }
      cache[i][j][k] = res
      return res
    }
  }

  return dfs(1, 2, 0)
}

Case

test.each([
  {
    input: {
      graph: [[5, 6], [3, 4], [6], [1, 4, 5], [1, 3, 5], [0, 3, 4, 6], [0, 2, 5]],
    },
    output: 2,
  },
  {
    input: {
      graph: [
        [2, 3, 4],
        [2, 4],
        [0, 1, 4],
        [0, 4],
        [0, 1, 2, 3],
      ],
    },
    output: 2,
  },
  { input: { graph: [[2, 3], [2], [0, 1], [0, 4], [3]] }, output: 2 },
  {
    input: {
      graph: [
        [3, 4],
        [3, 5],
        [3, 6],
        [0, 1, 2],
        [0, 5, 6],
        [1, 4],
        [2, 4],
      ],
    },
    output: 0,
  },
  { input: { graph: [[2, 5], [3], [0, 4, 5], [1, 4, 5], [2, 3], [0, 2, 3]] }, output: 0 },
  { input: { graph: [[1, 3], [0], [3], [0, 2]] }, output: 1 },
])('input: graph = $input.graph', ({ input: { graph }, output }) => {
  expect(catMouseGame(graph)).toEqual(output)
})