本题解采用了搜索和评估的策略来预测五子棋的输赢情况。核心思路是通过哈希表记录各类直线（水平、垂直、两个对角线）上的棋子位置。通过这种数据结构可以快速地评估和更新棋局。具体方法包括：1. 初始化黑白棋的数据结构来记录棋子位置；2. 为每种颜色的棋子定义添加函数，便于更新棋局；3. 评估每种直线上的棋子配置，查找可以直接赢得比赛的落子点；4. 根据当前棋局使用最优策略预测接下来的三步棋，包括黑白双方的最优防守和进攻。根据棋局动态评估，判断棋局的输赢情况。
时间复杂度: O(m * n * log n)
空间复杂度: O(n)
from sortedcontainers import SortedList
from collections import defaultdict
class Solution:
def gobang(self, pieces: List[List[int]]) -> str:
B = [defaultdict(SortedList) for _ in range(4)] # Black pieces lines: horizontal, vertical, diagonal with slope 1 and -1
W = [defaultdict(SortedList) for _ in range(4)] # White pieces lines
def add_piece(x, y, c):
P = W if c else B # Select color array
P[0][y].add(x) # Add to horizontal line
P[1][x].add(y) # Add to vertical line
P[2][y - x].add(x) # Add to diagonal line slope 1
P[3][y + x].add(x) # Add to diagonal line slope -1
def get_pos(k, v, d): # Helper to get the actual position based on line and index
if d == 0: x, y = v, k
elif d == 1: x, y = k, v
elif d == 2: x, y = v, k + v
elif d == 3: x, y = v, k - v
return (x, y)
# Search for winning moves, where adding a piece leads to a victory
def find_win_ps(P, Q, np) -> defaultdict(set):
win_points = defaultdict(set)
for d in range(4):
for k in P[d]:
ps, n = P[d][k], len(P[d][k])
if n < np: continue # Not enough pieces to form a line
for i in range(n + 1 - np):
dif = ps[i + np - 1] - ps[i]
if dif < 5: # Potential win by filling gaps
vs = [v for v in range(ps[i] + dif - 4, ps[i] + 5) if v not in ps[i:i + np] and not has_piece(Q, (k, v, d))]
nvs = len(vs)
if nvs < 5 - np: continue # Not enough spots to win
dt = 4 - np
for j in range(nvs - dt):
v1, v2 = vs[j], vs[j + dt]
if v2 - v1 > 4: continue # Too far apart to form a line
xy1, xy2 = get_pos(k, v1, d), get_pos(k, v2, d)
win_points[xy1].add(xy2)
win_points[xy2].add(xy1)
if np == 4 and len(win_points) > 1: return win_points # Immediate win for 4 in a row
return win_points
def has_piece(X, kvd) -> bool: # Check if a position is occupied
k, v, d = kvd
return k in X[d] and v in X[d][k]
for x, y, c in pieces:
add_piece(x, y, c) # Add initial pieces to the board
if len(find_win_ps(B, W, 4)) > 0:
return 'Black' # Black wins with a potential 5 in a row
live_w4 = find_win_ps(W, B, 4)
if len(live_w4) > 1:
return 'White' # White wins if multiple 4 in a row options exist
if len(live_w4) == 1:
x, y = list(live_w4.keys())[0]
add_piece(x, y, 0) # Block white's potential 4 in a row
return 'Black' if len(find_win_ps(B, W, 4)) > 1 else 'None' # Check if blocking leads to a new win or a draw
return 'Black' if any(len(ds) > 1 for ds in find_win_ps(B, W, 3).values()) else 'None' # Check for possible double 4's for black