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

Problem Info

USACO 2017 US Open Bronze Problem 3 Modern Art Problem Link

My Work

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

# Get all possible colors, which is everything visible excluding zero
possible = set()
for row in grid:
	for p in row:
if 0 in 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)
	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:
		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))

		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:

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


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:


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

What I’ve Tried

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.

It is impossible that 2 was the first color painted. Can you see why?

Yes! Thank you