Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Greedy Coloring with Direct Propagation | T(C + E), S(C + E) solution in Speedy category for Color Map by mmartsinenko
def color_map(region):
NEIGHBORS = ((-1, 0), (1, 0), (0, -1), (0, 1)) # Directions: Up, Down, Left, Right
rows, cols = len(region), len(region[0])
# Step 1: Build adjacency list (country -> set of neighbors)
adjacency = {region[i][j]: set() for i in range(rows) for j in range(cols)}
for i in range(rows):
for j in range(cols):
country = region[i][j]
for di, dj in NEIGHBORS:
ni, nj = i + di, j + dj
if 0 <= ni < rows and 0 <= nj < cols:
neighbor = region[ni][nj]
if neighbor != country:
adjacency[country].add(neighbor)
# Step 2: Assign colors iteratively
num_countries = len(adjacency)
colors = [-1] * num_countries # Colors assigned to each country
for country in range(num_countries):
# Find all colors used by neighbors
neighbor_colors = {colors[neighbor] for neighbor in adjacency[country] if colors[neighbor] != -1}
# Assign the smallest color not used by neighbors
for color in range(1, 5):
if color not in neighbor_colors:
colors[country] = color
break
return colors
Dec. 21, 2024
