問題資訊
USACO 2017 美國公開賽銅牌問題 3 現代藝術問題鏈接
我的作業
# 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，這是正確答案。這就是我的問題。我不知道為什么是 3 而不是 4
我試過的
我已經多次閱讀該問題，但我仍然不明白。
如果有人能幫忙解釋一下，那就太好了。
uj5u.com熱心網友回復：
我相信這個問題的一個重要部分是識別輸入中的“破碎”矩形（即有重疊的矩形）。在上一個示例的情況下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
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/361612.html