---

1275. 找出井字棋的获胜者

• 标签：数组、哈希表、矩阵、模拟
• 难度：简单

题目链接

• 1275. 找出井字棋的获胜者 - 力扣

题目大意

描述：井字棋是由两个玩家 A 和 B 在 $3 \times 3$ 的棋盘上进行的游戏。游戏规则如下：

• 玩家轮流将棋子放在空方格上。
• 第一个玩家 A 总是用 'X' 作为棋子，第二个玩家 B 总是用 'O' 作为棋子。
• 只要有 $3$ 个相同的棋子排成一条直线（行、列、对角线），游戏结束。
• 如果所有方格都放满棋子，游戏也会结束。

给你一个数组 $moves$，其中 $moves[i] = [row_i, col_i]$ 表示第 $i$ 次移动的位置。

要求：

• 如果游戏存在获胜者（A 或 B），返回该游戏的获胜者。
• 如果游戏以平局结束，返回 "Draw"。
• 如果仍会有行动（游戏未结束），返回 "Pending"。

说明：

• $1 \le moves.length \le 9$。
• $moves$ 都是有效的，网格最初是空的，A 先行动。

示例：

• 示例 1：

输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出："A"
解释："A" 获胜，他总是先走。

• 示例 2：

输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
输出："B"
解释："B" 获胜。

解题思路

思路 1：模拟

1. 核心思想

直接模拟游戏过程：按照 $moves$ 的顺序在棋盘上落子，A 走一步、B 走一步。每走一步后检查当前玩家是否获胜。如果所有棋子都下完了还没人赢，就根据棋盘是否满来判断是平局还是未结束。

获胜检查：因为棋盘是 $3 \times 3$ 的固定大小，只有 $8$ 种赢法：$3$ 行、$3$ 列、$2$ 条对角线。每次落子后枚举这 $8$ 种情况即可。

2. 具体步骤

第 1 步：初始化棋盘

创建一个 $3 \times 3$ 的整数矩阵 $grid$，全为 $0$。用 $1$ 表示 A 的棋子，$-1$ 表示 B 的棋子。

第 2 步：依次落子并检查

遍历 $moves$，偶数下标是 A 的步（值为 $1$），奇数下标是 B 的步（值为 $-1$）。

每次落子后，检查当前玩家是否获胜：

• 遍历行 $0$ 到 $2$，检查整行的值是否都是当前玩家的值。
• 遍历列 $0$ 到 $2$，检查整列的值是否都是当前玩家的值。
• 检查主对角线 $(0,0)-(1,1)-(2,2)$。
• 检查副对角线 $(0,2)-(1,1)-(2,0)$。

如果获胜，返回 "A" 或 "B"。

第 3 步：处理平局和未完成

遍历完所有 $moves$ 后仍未有人获胜：

• 如果 $moves.length == 9$，说明 $3 \times 3$ 棋盘已满，返回 "Draw"。
• 否则棋盘还有空位，返回 "Pending"。

结合示例 1 走一遍：

$moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]$

A：$(0,0)$，棋盘 $\begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix}$ → 不赢
B：$(2,0)$，棋盘 $\begin{bmatrix}1&0&0\\0&0&0\\-1&0&0\end{bmatrix}$ → 不赢
A：$(1,1)$，棋盘 $\begin{bmatrix}1&0&0\\0&1&0\\-1&0&0\end{bmatrix}$ → 不赢
B：$(2,1)$，棋盘 $\begin{bmatrix}1&0&0\\0&1&0\\-1&-1&0\end{bmatrix}$ → 不赢
A：$(2,2)$，棋盘 $\begin{bmatrix}1&0&0\\0&1&0\\-1&-1&1\end{bmatrix}$ → 检查列 $0$：$1,0,-1$ 不赢；检查对角线：$(0,0)=1,(1,1)=1,(2,2)=1$ 都是 A → A 获胜！

思路 1：代码

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        # 棋盘，1 表示 A，-1 表示 B，0 表示空
        grid = [[0] * 3 for _ in range(3)]

        # 轮流落子
        for i, (r, c) in enumerate(moves):
            player = 1 if i % 2 == 0 else -1
            grid[r][c] = player

            # 检查当前玩家是否获胜
            for j in range(3):
                # 检查第 j 行和第 j 列
                if (grid[j][0] == grid[j][1] == grid[j][2] == player or
                    grid[0][j] == grid[1][j] == grid[2][j] == player):
                    return "A" if player == 1 else "B"
            # 检查两条对角线
            if (grid[0][0] == grid[1][1] == grid[2][2] == player or
                grid[0][2] == grid[1][1] == grid[2][0] == player):
                return "A" if player == 1 else "B"

        # 没有获胜者，判断平局还是未完成
        return "Draw" if len(moves) == 9 else "Pending"

思路 1：复杂度分析

• 时间复杂度：$O(1)$。棋盘大小固定为 $3 \times 3$，最多 $9$ 步操作。每次落子后的检查也是常数时间。
• 空间复杂度：$O(1)$，只需要存储 $3 \times 3$ 的棋盘，固定大小。