PAST5G
マス目を頂点とし、隣接してるマス目は辺で結んだグラフを考える
頂点は高々16個と小さい
グラフの各頂点を始点として「すべての頂点を通るパス」をDFS
これの計算量を理論的に見積もれてないけど、小さいからいけるだろう的判断
与えられたマス目が1個の時、グラフに辺が0本になる。これがコーナーケースでWAした
(1) で手当てしたが、これはそもそも頂点のリストを作ってないところに問題がある
「辺が双方向だから辺の始点の集合が頂点の集合だろう」→間違い、辺がないケースがある
地図は地図読み込み時に番兵をつけるで読んでる
隣接関係でグラフにするところはライブラリ化してもいいかもな
pythondef solve(H, W, data):
from collections import defaultdict
# make graph
edges = defaultdict(list)
count = 0
a_vertex = None
for x in range(H):
for y in range(W):
v = W * x + y
pos = WIDTH + 1 + WIDTH * x + y
if data[pos]:
a_vertex = v
count += 1
if data[pos + 1]:
edges[v].append(v + 1)
edges[v + 1].append(v)
if data[pos + WIDTH]:
edges[v].append(v + W)
edges[v + W].append(v)
if count == 1: # (1)
print(1)
v = a_vertex
x, y = divmod(v, W)
print(x + 1, y + 1)
for start in edges:
visited = [False] * (H * W)
path = []
def visit(cur):
visited[cur] = True
path.append(cur)
if len(path) == count:
return True
for next in edges[cur]:
if not visited[next]:
r = visit(next)
if r:
return True
visited[cur] = False
path.pop()
if visit(start):
print(count)
for v in path:
x, y = divmod(v, W)
print(x + 1, y + 1)
returnRelated Pages
- →地図読み込み時に番兵をつける×数列を有理式にする×ラグランジュ補間×対称性で次元削減×余事象を引く×未ac×足し算の順序を変える×xごとのf(x,y)の和はyごとのf(x,y)の和×最大値の期待値×順位統計量×maxの不等号は不等号のand×0,1→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]