[Python] Why does my approach return incorrect result on Kattis Grid Game problem?

I'm working on the Grid Game problem on Kattis.

Problem Summary:


You are given an N × N grid of integers. You must choose exactly N cells, such that:

• No two selected cells are in the same row.
• No two selected cells are in the same column.
• From the N chosen values, compute the minimum.
• Your goal is to get the maximum of these minimum values.

Sample Input:


The first line of input consists of an integer N (height of the grid). The next N lines each contains N integers, representing the grid.

3
3 1 4
1 5 1
2 9 1

Sample Output:


2

My Approach:


Here is my Python code:

N = int(input())
grid = []
for _ in range(N):
grid.append(list(map(int, input().split())))

m = [] #initiate to store the minimums

for i in range(N): # Try using column i as starting point
L = []
used_rows = [False] * N
used_cols = [False] * N

# Pick the value at (0, i)
L.append(grid[0])
used_rows[0] = True
used_cols = True

count = 1 # Already picked 1 value

for col in range(N):
if used_cols[col]:
continue
for row in range(N):
if used_rows[row]:
continue
# Pick the available (row, col) not used
L.append(grid[row][col])
used_rows[row] = True
used_cols[col] = True
count += 1
break # move to next column

if count == N:
break

if len(L) == N:
m.append(min(L))

print(max(m))

My Question:


For the sample input above, my code outputs 1 instead of 2. What's wrong in my logic? How can I fix it? I know some other ways to solve it like using permutations, but I wanted to do it like this way.

Continue reading...