Official
F - Fractal and Palindrome Editorial by hos_lyric
(より詳しい解説は後日ブログで公開します)
内側の \(2\) 個の正方形のうち,左上側を 1
,右下側を 2
とします.
迷路を観察すると,内側に深く潜り,中央の D
の道を通り,外側に出ていく,という流れであることがわかります.これを入口と出口から同時に辿ると,1
と 2
のどちらを選んでいったかという列が一致する必要があります.
迷路を整理すると,
A
を使い,入口からは211
,出口からは2
と選ぶB
を使い,入口からは1
,出口からは211
と選ぶC
を使い,入口からは2
,出口からは1
と選ぶ
のいずれかを繰り返すという形になっていることがわかります.
これは Post の対応問題のインスタンスです.一般的な解法は存在しないので,適当な方法で探索することになります.例えば,入口からと出口からの 1
/2
列の差 (余っている suffix) が十分短い解が存在するので,それを状態としてグラフ探索をすると上手くいきます.
posted:
last update: