1240.铺瓷砖.md

1240.铺瓷砖

/*
 * @lc app=leetcode.cn id=1240 lang=typescript
 *
 * [1240] 铺瓷砖
 */

// @lc code=start
function tilingRectangle(n: number, m: number): number {}
// @lc code=end

解法 1: dfs

function tilingRectangle(n: number, m: number): number {
  if (n === 1) return m
  if (m === 1) return n
  if (n > m) return tilingRectangle(m, n)
  const g: number[] = new Array(n).fill(0)
  const max = (1 << m) - 1
  let res = Infinity
  const dfs = (i: number, sum = 0) => {
    while (g[i] === max) i--
    if (i < 0) {
      res = Math.min(res, sum)
      return
    }
    if (sum >= res) return
    for (let j = 0, k = 0; j < m; j = ++k) {
      if (g[i] & (1 << j)) continue
      let len = 0
      for (; k < m; k++) {
        if (g[i] & (1 << k)) break
        len = k - j + 1
        if (len > i + 1) {
          k--
          len--
          break
        }
      }
      if (k >= m) k--

      {
        let state = ((1 << len) - 1) << j,
          cur = state,
          clear = ~state
        for (let a = len; a > 0; a--) {
          for (let t = 0; t < a; t++) {
            g[i - t] = (g[i - t] & clear) | cur
          }
          if (a < len) g[i - a] &= clear
          cur &= ~(1 << (j + a - 1))
          dfs(i, sum + 1)
        }
        g[i] &= clear
        k = len + j - 1
      }
    }
  }
  dfs(n - 1)
  return res
}

Case

test.each([
  { input: { n: 2, m: 3 }, output: 3 },
  { input: { n: 5, m: 8 }, output: 5 },
  { input: { n: 11, m: 13 }, output: 6 },
  { input: { n: 13, m: 12 }, output: 7 },
  { input: { n: 13, m: 1 }, output: 13 },
])('input: n = $input.n, m = $input.m', ({ input: { n, m }, output }) => {
  expect(tilingRectangle(n, m)).toEqual(output)
})