如何高效实现无限棋盘游戏中每次落子后的n连子胜负判定？

核心优化思路：局部缓存连续长度，避免全局扫描 #

不用每次落子后对四个方向做O(n)遍历，而是给每个已落子位置维护局部连续长度的缓存，仅在必要时更新关联位置的缓存，将单次判定复杂度降到O(1)。

数据结构设计 #

用哈希表（比如Python的dict、Java的HashMap）存储所有落子位置的信息，键为坐标元组(i,j)，值为包含四个字段的结构：

• left：当前位置向左（j递减方向）连续同色的棋子数（不含自身）
• right：当前位置向右（j递增方向）连续同色的棋子数（不含自身）
• up：当前位置向上（i递减方向）连续同色的棋子数（不含自身）
• down：当前位置向下（i递增方向）连续同色的棋子数（不含自身）

落子后的判定与缓存更新步骤 #

1. 记录当前落子的玩家颜色、坐标(x,y)，将该位置存入哈希表，初始四个字段设为0。
2. 计算当前位置的四个方向连续值：
   • 若(x, y-1)存在且为同色，left = 哈希表中(x,y-1)的left + 1；否则left=0
   • 若(x, y+1)存在且为同色，right = 哈希表中(x,y+1)的right + 1；否则right=0
   • 若(x-1, y)存在且为同色，up = 哈希表中(x-1,y)的up + 1；否则up=0
   • 若(x+1, y)存在且为同色，down = 哈希表中(x+1,y)的down + 1；否则down=0
3. 判定胜负：计算横向总连续长度left + right + 1，纵向总连续长度up + down + 1。若任意一个值≥n，当前玩家获胜。
4. 更新关联端点的缓存：
   • 横向：更新左端点(x, y - left)的right为left + right + 1；更新右端点(x, y + right)的left为left + right + 1
   • 纵向：更新上端点(x - up, y)的down为up + down + 1；更新下端点(x + down, y)的up为up + down + 1

方案优势 #

• 时间效率：单次落子后的判定与缓存更新都是O(1)操作，仅涉及固定数量的相邻位置与端点，无需遍历n个格子。
• 空间适配：哈希表仅存储有棋子的位置，完美适配无限棋盘的需求，空间复杂度与落子总数成正比。
• 缓存更新可控：仅更新连续段的两个端点，不会触发大范围缓存更新，解决了你之前担心的缓存维护复杂度问题。

简单示例（n=3） #

假设玩家在(2,2)落子，同色棋子已有(2,1)和(2,3)：

1. 计算(2,2)的left=1（来自(2,1)的left+1），right=1（来自(2,3)的right+1）
2. 横向总长度=1+1+1=3，满足获胜条件，直接判定当前玩家获胜
3. 更新(2,1)的right为3，(2,3)的left为3，后续若在(2,0)落同色子，可直接读取(2,1)的right值快速计算连续长度。

内容的提问来源于stack exchange，提问作者roulette01