バックトラック法について
- 経路の全探索等で使える
- dfsで最初に状態をtrueにして、子ノードの探索が終わったらfalseになるなどして状態を管理する
例; 典型的なバックトラック法の例
問題
解説
- 任意の点から探索する
- バックトラック法を使わないとフラグ管理ができない
解答
H,W=map(int,input().split())
G = [list(input()) for _ in range(H)]
used = [[False] * W for _ in range(H)]
def dfs(sh, sw, ph, pw):
if sh == ph and sw == pw and used[ph][pw] == True:
return 0
used[ph][pw] = True
ret = -float("inf")
for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nh, nw = dh + ph, dw + pw
if not (0 <= nh < H and 0<= nw < W and G[nh][nw] == "."):
continue
if (not(sh == nh and sw == nw)) and used[nh][nw] == True:
continue
v = dfs(sh, sw, nh, nw)
ret = max(ret, v+1)
used[ph][pw] = False
return ret
ans = 0
for h in range(H):
for w in range(W):
ans = max(ans, dfs(h, w, h, w))
if ans <= 2:
print(-1)
else:
print(ans)
例; 経路のパターンの全探索
- 特定のゴールを持たず、経路の大きさが評価対象
- 経路の大きさを見るので、通ってきた経路を保存する変数が必要なる
- 通った経路情報はlistでは保存できないほど大きくなるので通った経路を2進数で表現したintで表現する
問題
解答
import sys; sys.setrecursionlimit(10**9)
import collections
N = int(input())
K = int(input())
G = [list(input()) for i in range(N)]
ans = 0
vis = collections.defaultdict(lambda :False)
done = set()
def dfs( h, w, v, prev):
global ans
vis[(h, w)] = True
idx = N*h + w
v += 1 << idx
if v in done:
return
done.add(v)
if len(prev) == K:
ans += 1
return
for ph, pw in prev:
for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nh, nw = ph+dh, pw+dw
if 0 <= nh < N and 0 <= nw < N and G[nh][nw] == '.' and not vis[(nh, nw)]:
prev.append((nh, nw))
dfs(nh, nw, v, prev)
prev.pop()
vis[(nh, nw)] = False
for h in range(N):
for w in range(N):
if 0 <= h < N and 0 <= w < N and G[h][w] == '.':
vis = collections.defaultdict(lambda :False)
dfs(h, w, 0, [(h, w)])
print(ans)