CP Python 现代艺术的逻辑混乱（Bronze USACO 2017 美国公开赛第 3 页）

Question

问题信息

USACO 2017美网铜牌问题3现代艺术Problem Link

我的作品

# 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 而不是 3，这是正确答案。这就是我的问题。我不知道为什么它是 3 而不是 4

我试过的

这个问题我看了很多遍，还是没明白。

谁能帮忙解释一下就好了

Answer 1

我认为这个问题的一个重要部分是识别输入中的“破损”矩形（即有重叠的矩形）。对于上一个示例，1、2 和 4 是“完整的”矩形，因为它们没有被任何其他图块明确重叠。然而，3 显然与 2 重叠，因此，2 或 3 先存在，而不是同时存在。因此，有两个完整的加上一组不完整的，最终结果为3。以下是此问题的可能解决方案的代码：

from collections import defaultdict
def w_h(points):
   d = {'w':set(), 'h':set()}
   for a, b in points:
      d['h'].add(a)
      d['w'].add(b)
   return [max(b) - min(b) + 1 for b in d.values()]

def original_paintings(p):
  d = defaultdict(list)
  for x, a in enumerate(p):
     for y, s in enumerate(a):
        if s:
           d[s].append((x, y))
  r = {a:(wh:=w_h(b))[0]*wh[1] - len(b) for a, b in d.items()}
  return len(r) - len(set(r.values())) + 1

t1 = [[2, 2, 3, 0], [2, 7, 3, 7], [2, 7, 7, 7], [0, 0, 0, 0]]
t2 = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 3, 3, 4]]
print(original_paintings(t1))
print(original_paintings(t2))

输出：

1
3

Answer 2

我问过我的老师，他给了我这个：

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)]

rect=[]
for clr in range(10):
    rect.append([n,n,-1,-1])

# Find out rect for each color
for i in range(n):
    for j in range(n):
        a=grid[i][j]
        if a>0:
            rect[a][0]=min(rect[a][0],i)
            rect[a][1]=min(rect[a][1],j)
            rect[a][2]=max(rect[a][2],i)
            rect[a][3]=max(rect[a][3],j)

ans=0
not_original=[0]*10
for clr in range(10):
    if rect[clr][0]<n:
        ans=ans+1
        # any color inside another rect cannot be original color
        for i in range(rect[clr][0], rect[clr][2]+1):
            for j in range(rect[clr][1], rect[clr][3]+1):
                if grid[i][j]!=clr:
                    not_original[grid[i][j]]=1

with open("art.out", 'w') as fout:
    fout.write(str(ans-sum(not_original)))

主要区别在于我忘记了每个矩形可能看起来像

**6
**6
*66

我的程序没有考虑底部中间 6。

CP Python 现代艺术的逻辑混乱（Bronze USACO 2017 美国公开赛第 3 页）

CP Python Logic Confusion on Modern Art (Bronze USACO 2017 US Open p.3)

python

algorithm

recursion

logic

问题信息

我的作品

问题

我试过的