794.有效的井字游戏.md

794.有效的井字游戏

/*
 * @lc app=leetcode.cn id=794 lang=typescript
 *
 * [794] 有效的井字游戏
 */

// @lc code=start
function validTicTacToe(board: string[]): boolean {}
// @lc code=end

解法 1: 模拟

function validTicTacToe(board: string[]): boolean {
  let countx = 0,
    counto = 0,
    winx = false,
    wino = false,
    dirs: [number, number][] = [
      [0, 1],
      [1, 0],
      [1, 1],
      [1, -1],
    ]

  // 判断是否有同一个方向上有连续相同的三个棋子
  const dfs = (i: number, j: number) => {
    let s = board[i]?.[j]
    for (let k = 0; k < dirs.length; k++) {
      const [x, y] = dirs[k]
      let flag = true
      for (let l = 0; l < 2; l++) {
        if (board[i + x * (l + 1)]?.[j + y * (l + 1)] !== s) flag = false
      }
      if (flag) return true
    }

    return false
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === ' ') continue

      let flag = false
      if (i === 0 || j === 0) flag = dfs(i, j)

      if (board[i][j] === 'O') {
        countx++
        wino = wino || flag
      } else {
        counto++
        winx = winx || flag
      }
    }
  }

  // 因为 x 先走,所以 x 一定和 o 相等,或者比 o 大 1
  if (counto !== countx && counto - countx !== 1) return false
  // 如果 x 赢,则 x 比 o 大 1;如果 o 赢,则 x 等于 o
  if ((winx && counto - countx !== 1) || (wino && counto !== countx)) return false
  // 其实可以不用检测两个同时赢的情况,这种情况通不过上一个 if
  // if (flagx && flago) return false

  return true
}

Case

test.each([
  { input: { board: ['O  ', '   ', '   '] }, output: false },
  { input: { board: ['XOX', ' X ', '   '] }, output: false },
  { input: { board: ['XXX', '   ', 'OOO'] }, output: false },
  { input: { board: ['XOX', 'O O', 'XOX'] }, output: true },
  { input: { board: ['XXX', 'OOX', 'OOX'] }, output: true },
  { input: { board: ['XXX', 'XOO', 'OO '] }, output: false },
  { input: { board: ['XOX', 'XO ', ' OX'] }, output: false },
  { input: { board: ['XXO', 'XOX', 'OXO'] }, output: false },
  { input: { board: ['XOX', 'OXO', 'XXO'] }, output: true },
])('input: board = $input.board', ({ input: { board }, output }) => {
  expect(validTicTacToe(board)).toEqual(output)
})