USACO 2017 US Open Bronze Problem 3 Modern Art 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)))
My logic is pretty clear from the code, and I can get 6 out of 10 test cases, but when I try an input like:
4 1234 1234 1234 1334
My program outputs 4 instead of 3, which is the correct answer. Therein lies my problem. I have no idea why it is 3 and not 4
I’ve read over the problem multiple times, and I still don’t get it.
If anyone could help explain it, that would be great.