Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Color Map by han97
# migrated from python 2.7
def color_map(region):
def init_graph():
moves = ((-1, 0), (1, 0), (0, -1), (0, 1))
n, m = len(region), len(region[0])
def get_neighbors(row, col):
for x, y in moves:
new_x = row + x
new_y = col + y
if 0 <= new_x < n and 0 <= new_y < m and region[new_x][new_y] != region[row][col]:
yield region[new_x][new_y]
country_number = max(max(row) for row in region) + 1
graph = [set() for _ in range(country_number)]
for i in range(n):
for j in range(m):
for x in get_neighbors(i, j):
graph[region[i][j]].add(x)
return country_number, graph
country_number, graph = init_graph()
def get_max_independent_set(used): # works for O(n**2)
def get_independent_set(v):
if v in used:
return {}
s = {v}
for i, u in enumerate(graph):
if i not in used and not (s & u):
s.add(i)
return s
return max((get_independent_set(i) for i, v in enumerate(graph)), key=len)
res = [0] * country_number
def get_result(used=set(), color=1):
if len(used) != len(graph):
max_set = get_max_independent_set(used)
for i in max_set:
res[i] = color
get_result(used | max_set, color + 1)
get_result()
return res
Aug. 14, 2016
