Bloomberg Connect Four：静态棋盘四方向连续四子计数

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版只计算给定静态 grid，不模拟下落；'.' 为空位。
• 每条长度恰 4 的相同非空窗口计 1，长度 5 会产生 2 个重叠窗口；若面试是计每条极大连线或每个落子位置，输出不同。

解题路线

1. 遍历每个非空格作为候选起点，只看向右、下、右下、左下四方向，避免反向重复计。
2. 端点 (r+3dr,c+3dc) 在范围内才比较中间 3 格；所有字符同起点即可计数。
3. 逐方向 dry run 横线、斜线、长度 5 重叠和交叉线；若棋盘要符合重力规则，另检查每列不存在悬空棋子。
4. 如果需要模拟新棋子落下，先按列找到最低空格，再只检查经过新位置的窗口，复杂度可大幅低于整盘扫描。

手动走一遍

一行 AAAAA 有两个长度 4 窗口 [0..3] 与 [1..4]，训练版得 2；如果题意是一个胜利连线，则应改为 1，需面试现场确认。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def count_four_windows(grid, empty="."):
    """Count length-four equal nonempty windows in four line directions."""
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")
    count = 0
    for r in range(rows):
        for c in range(cols):
            token = grid[r][c]
            if token == empty:
                continue
            for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)):
                end_r, end_c = r + 3 * dr, c + 3 * dc
                if 0 <= end_r < rows and 0 <= end_c < cols:
                    if all(grid[r + k * dr][c + k * dc] == token for k in range(1, 4)):
                        count += 1
    return count

复杂度

R×C 格子各最多比较 4×3 个邻格，O(RC) 时间、O(1) 附加空间；若输出所有窗口需 O(W) 存储。

易错点与追问

容易失分的边界

• 八方向都扫导致重复一条线。
• 空字符也被计四连。
• 长度 5 的重叠口径未澄清。
• 把已有 grid 问题擅自改为落子搜索。

继续深挖

• 若只判断有无胜者？
• 若每次新增一个落子，如何增量判断？
• 若两个方向交叉算几处？