Deloitte | COGNIZANT | IBM | CAPGEMINI
def solve(N, M, grid, K):
def is_star(r, c, grid):
val = grid[r][c]
if val == 0:
return False
for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
nr, nc = r + dr, c + dc
if not (0 <= nr < N and 0 <= nc < M):
return False
if grid[nr][nc] != val:
return False
return True
def check_win(grid):
for r in range(1, N-1):
for c in range(1, M-1):
if is_star(r, c, grid):
return True
return False
def serialize(grid):
return tuple(tuple(row) for row in grid)
def dfs(state, turn):
grid = [list(row) for row in state]
if check_win(grid):
return (0, 1, 0) if turn == 1 else (0, 0, 1)
moves = [(r, c) for r in range(N) for c in range(M) if grid[r][c] == 0]
if not moves:
return (1, 0, 0)
total = [0, 0, 0]
for r, c in moves:
for fruit in range(1, K+1):
grid[r][c] = fruit
res = dfs(serialize(grid), 1 - turn)
for i in range(3):
total[i] += res[i]
grid[r][c] = 0 # backtrack
return tuple(total)
result = dfs(serialize(grid), 0)
print(*result)
The game of grid✅✅
1.2K ·