Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS solution in Clear category for Color Map by Slavin
def paint(reg, near, colors):
if reg < 0: return colors
for color in range(1, 5):
if all(colors[rg] != color for rg in near[reg]):
colors[reg] = color
if paint(reg-1, near, colors): return colors
colors[reg] = 0
def color_map(R):
H, W = len(R), len(R[0])
N = max(max(row)for row in R) + 1
near = [set()for reg in range(N)]
for i in range(H):
for j, reg in enumerate(R[i]):
for k, l in (i,j-1), (i,j+1), (i-1,j), (i+1,j):
if 0 <= k < H and 0 <= l < W and R[k][l] != reg:
near[reg].add(R[k][l])
return paint(N-1, near, [0]*N)
Nov. 12, 2025
