跳转至

LeetCode: 794. 有效的井字游戏

1、题目描述

用字符串数组作为井字游戏的游戏板 board。当且仅当在井字游戏过程中,玩家有可能将字符放置成游戏板所显示的状态时,才返回 true

该游戏板是一个 3 x 3 数组,由字符 " ","X""O" 组成。字符 " " 代表一个空位。

以下是井字游戏的规则:

玩家轮流将字符放入空位(" ")中。 第一个玩家总是放字符 “X”,且第二个玩家总是放字符 “O”“X”“O” 只允许放置在空位中,不允许对已放有字符的位置进行填充。 当有 3 个相同(且非空)的字符填充任何行、列或对角线时,游戏结束。 当所有位置非空时,也算为游戏结束。 如果游戏结束,玩家不允许再放置字符。

示例 1:

输入: board = ["O  ", "   ", "   "]
输出: false
解释: 第一个玩家总是放置“X”。

示例 2:

输入: board = ["XOX", " X ", "   "]
输出: false
解释: 玩家应该是轮流放置的。

示例 3:

输入: board = ["XXX", "   ", "OOO"]
输出: false

示例 4:

输入: board = ["XOX", "O O", "XOX"]
输出: true

说明:

说明:

  • 游戏板 board 是长度为 3 的字符串数组,其中每个字符串 board[i] 的长度为 3。
  • board[i][j] 是集合 {" ", "X", "O"} 中的一个字符。

2、解题思路

  • 首先统计XO的数量

  • 然后判断两个人是否能赢

  • 下面的条件表示不能赢:

  • 同时赢

  • O的数量大于X的数量
  • X的数量比O的数量多于1
  • X获胜的时候,数量一样多
  • O获胜的时候,XO

其他情况表示可以获得

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        row, col = len(board), len(board[0])
        temp = [[0 for _ in range(col)] for _ in range(row)]

        count_x = 0
        count_o = 0

        row_sum = [0] * 3
        col_sum = [0] * 3
        diagonal = [0] * 2
        for i in range(row):
            for j in range(col):
                if board[i][j] == "X":
                    count_x += 1
                    temp[i][j] = 1
                    col_sum[j] += 1
                    row_sum[i] += 1
                elif board[i][j] == "O":
                    count_o += 1
                    temp[i][j] = -1
                    col_sum[j] -= 1
                    row_sum[i] -= 1
        diagonal[0] = temp[0][0] + temp[1][1] + temp[2][2]
        diagonal[1] = temp[2][0] + temp[1][1] + temp[0][2]

        if count_o > count_x or count_x - count_o > 1:
            return False
        x_win = False
        o_win = False

        sum_set = set(row_sum + col_sum + diagonal)
        if 3 in sum_set:
            x_win = True
        if -3 in sum_set:
            o_win = True

        if x_win and o_win or x_win and count_x == count_o or o_win and count_x > count_o:
            return False

        return True