1377.t-秒后青蛙的位置.md

1377.t-秒后青蛙的位置

/*
 * @lc app=leetcode.cn id=1377 lang=typescript
 *
 * [1377] T 秒后青蛙的位置
 */

// @lc code=start
function frogPosition(n: number, edges: number[][], t: number, target: number): number {}
// @lc code=end

解法 1: dfs

function frogPosition(n: number, edges: number[][], t: number, target: number): number {
  if (n === 1) return 1
  const g: number[][] = Array.from({ length: n + 1 }, () => [])
  for (let [u, v] of edges) {
    g[u].push(v)
    g[v].push(u)
  }
  let res = -1
  const dfs = (u: number, pre = -1, t: number, p: number) => {
    if (u === target) {
      if (t === 0 || (pre === -1 && g[u].length === 0) || (pre !== -1 && g[u].length === 1)) res = p
      else res = 0
      return
    }
    if (res !== -1) return
    if (!t) return
    if (pre === -1) p /= g[u].length
    else p /= g[u].length - 1
    for (let v of g[u]) {
      if (v === pre) continue
      dfs(v, u, t - 1, p)
    }
  }
  dfs(1, -1, t, 1)
  return res === -1 ? 0 : res
}

Case

test.each([
  {
    input: {
      n: 7,
      edges: [
        [1, 2],
        [1, 3],
        [1, 7],
        [2, 4],
        [2, 6],
        [3, 5],
      ],
      t: 2,
      target: 4,
    },
    output: 0.16666666666666666,
  },
  {
    input: {
      n: 7,
      edges: [
        [1, 2],
        [1, 3],
        [1, 7],
        [2, 4],
        [2, 6],
        [3, 5],
      ],
      t: 1,
      target: 7,
    },
    output: 0.3333333333333333,
  },
])(
  'input: n = $input.n, edges = $input.edges, t = $input.t, target = $input.target',
  ({ input: { n, edges, t, target }, output }) => {
    expect(frogPosition(n, edges, t, target)).toEqual(output)
  },
)