题目重点：只从新落子向四轴扩展检查连续 k，解释 O(k) move 与随机 AI 自动对弈的终止条件。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 两名玩家标为 1/2，横/竖/两条对角线任一方向存在连续 k 子即胜；只需在新落子位置检查，因为此前棋盘无胜者。
- 示例代码采用 的显式 player 接口；有效性由代码额外检查以便测试，题目保证 move 有效。自动轮换与棋盘格式、随机 AI 属于 的另一个接口变体，未写入同一函数签名。
解题路线
- 存 m×n 棋盘与当前胜者/已下步数。move 后从新格向每条轴两个反方向数相同棋子，最多各走 k−1 格；两侧长度相加再加新格达到 k 即胜。
- 不能用整行/整列计数判断任意连续 k：同一行的两个不相邻棋子会被误算。若 k 恰等于正方形棋盘边长且要求整行整列，才可用 O(1) 行/列/对角累计。
- 随机 AI 变体要从合法空格均匀或按定义抽样，交替落子直到 winner 或棋盘满；满盘无胜即 draw，不能让 AI 无限循环。输出棋盘格式先按那轮接口确认。
- 大棋盘稀疏落子可用坐标→玩家 map，单次检查仍 O(k)；并发对局需锁住验证空格、落子和胜负检查这一事务。
手动走一遍
在 3×5 棋盘 k=3，玩家 1 已占 (1,1) 与 (1,3)，在 (1,2) 落子后水平方向左右各见一子，连续长度 3 获胜；仅有 (1,1) 与 (1,3) 时计数为 2 却不连续。若所有 15 格填满仍无人满足 k，则是平局。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""m x n TicTacToe; player 1/2, k consecutive in any of four axes.
Core move(row,col,player) implements the stated move rules. Invalid moves are rejected
for a robust training implementation, though that post guarantees validity.
"""
class TicTacToe:
def __init__(self, rows: int, cols: int, k: int):
if rows <= 0 or cols <= 0 or not 1 <= k <= max(rows, cols):
raise ValueError('invalid board or win length')
self.rows, self.cols, self.k = rows, cols, k
self.board = [[0] * cols for _ in range(rows)]
self.winner = 0
self.moves = 0
def move(self, row: int, col: int, player: int) -> int:
if self.winner or player not in (1, 2) or not (0 <= row < self.rows and 0 <= col < self.cols) or self.board[row][col]:
raise ValueError('invalid move')
self.board[row][col] = player
self.moves += 1
for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)):
length = 1
for sign in (-1, 1):
r, c = row + sign * dr, col + sign * dc
while 0 <= r < self.rows and 0 <= c < self.cols and self.board[r][c] == player and length < self.k:
length += 1
r += sign * dr
c += sign * dc
if length >= self.k:
self.winner = player
break
return self.winner
def draw(self) -> bool:
return self.winner == 0 and self.moves == self.rows * self.cols
复杂度
初始化 O(mn) 时间/空间；每 move 最多沿四轴各两方向检查 k−1 步，O(k) 时间/O(1) 额外空间。若随机 AI 每步扫描所有空格，额外 O(mn)；维护空格集合可优化抽样但需同步更新。
易错点与追问
容易失分的边界
- 把同一行总数当连续长度。
- 只检查横竖，漏两条对角线。
- 边界之外读取或 k=1 特例错误。
- 胜负已定后还继续落子。
- 随机 AI 未处理满盘平局。
- 把 的自动轮换接口硬塞进 的显式 player 签名。
继续深挖
- m,n 很大但落子稀疏怎样存？
- 自动轮换玩家与显式 player 参数如何设计防非法顺序？
- 随机 AI 怎样在 O(1) 均摊时间选空格？
- 多人同时请求同一对局时如何保证原子落子？
