USACO 2017 US Open铜组第三题Modern Art Python代码错误求解

USACO 2017 US Open Bronze组第三题 Modern Art 原题链接

# Read in grid as 2D array
with open("art.in", 'r') as fin:
    n = int(fin.readline().strip())
    grid = [[int(i) for i in fin.readline().strip()] for _ in range(n)]
print(grid)

# Get all possible colors, which is everything visible excluding zero
possible = set()
for row in grid:
    for p in row:
        possible.add(p)
if 0 in possible:
    possible.remove(0)
print(possible)

# Recursive search function that gets the maximum x of the triangle and maximum y of the triangle, which will be used further down the road to calculate whether or not it is a valid rectangle
def search(grid, i, j, v):
    global max_x, max_y, searched, area
    if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != v or (i, j) in searched:
        max_x = max(max_x, j)
        max_y = max(max_y, i)
        return
    searched.append((i, j))
    area += 1
    search(grid, i+1, j, v)
    search(grid, i-1, j, v)
    search(grid, i, j+1, v)
    search(grid, i, j-1, v)

# Use the search, and check if there is a possibility of the rectangle being covered. It it is covered, eliminate the rectangle that covers it from the list of possibilities.
searched = []
for i, row in enumerate(grid):
    for j, p in enumerate(row):
        if (i, j) in searched or not p:
            continue
        max_x = 0 
        max_y = 0
        # The area variable is uneeded. Using it for debugging
        area = 0
        search(grid, i, j, p)
        print(area, (max_x-j) * (max_y-i))
        print()

        for k in range(i, max_y):
            for l in range(j, max_x):
                if grid[k][l] != p and grid[k][l] in possible:
                    possible.remove(grid[k][l])

# Write the answer to the output file
with open("art.out", 'w') as fout:
    fout.write(str(len(possible)))

代码逻辑清晰，10个测试用例可通过6个，但输入如下测试用例时：

4
1234
1234
1234
1334

程序输出为4，正确答案为3，无法定位错误原因。

已反复阅读题目要求，仍未找到问题，恳请各位帮忙解释问题所在。

核心错误 #

你的代码用第一个遇到的颜色c的坐标(i,j)作为该颜色矩形的左上角，这个逻辑是错误的。以你给出的测试用例为例，颜色3的分布如下：

• 行0列2、行1列2、行2列2、行3列1、行3列2都是3
• 该颜色对应矩形的左边界是列1，但是行优先遍历时第一个遇到的3的坐标是(0,2)，你直接把j=2作为矩形左边界，导致遍历矩形时漏掉了列1的所有位置，自然没有发现颜色2出现在颜色3的矩形范围内，也就没有把不可能是底层颜色的2从候选集里删除，最终得到错误结果4。
  此外你遍历矩形用的range(i, max_y)和range(j, max_x)是左闭右开区间，会漏掉矩形的最后一行和最后一列。

修复方法 #

不需要用DFS搜索边界，直接全局统计每个颜色的四个边界即可：

1. 初始化四个字典，分别存储每个颜色的最小行min_r、最大行max_r、最小列min_c、最大列max_c
2. 遍历整个网格，更新每个颜色的四个边界值
3. 对每个颜色c，遍历它的完整矩形范围（从min_r[c]到max_r[c]+1，min_c[c]到max_c[c]+1），如果矩形内出现其他颜色d，就把d从候选集possible中移除
4. 最终possible的大小就是答案

修改后的核心代码示例：

from collections import defaultdict

min_r = defaultdict(lambda: n)
max_r = defaultdict(lambda: -1)
min_c = defaultdict(lambda: n)
max_c = defaultdict(lambda: -1)

# 统计每个颜色的四个边界
for i in range(n):
    for j in range(n):
        c = grid[i][j]
        if c == 0:
            continue
        min_r[c] = min(min_r[c], i)
        max_r[c] = max(max_r[c], i)
        min_c[c] = min(min_c[c], j)
        max_c[c] = max(max_c[c], j)

# 逐个检查每个颜色的矩形范围
for c in possible.copy():
    # 遍历c对应的完整矩形
    for i in range(min_r[c], max_r[c]+1):
        for j in range(min_c[c], max_c[c]+1):
            d = grid[i][j]
            if d != c and d in possible:
                possible.remove(d)

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