aoj2538:Stack Maze
解法
とりあえず、問題を統一的に解くために、入力を若干いじります。
例えば、下のような入力
a.#
#A#
#bB
に対して、行を2つ追加して
.##
a.#
#A#
#bB
##.
とします。
一番上に".###############"みたいなやつを追加して、一番下に"############."みたいなやつを追加しています。
こうすると、必ず左上と右下が'.'になります。
上記の例でもう少し考察をします。
真ん中らへんにある'a'->'A'となるパスを作れそうなところを抜き出します。
a.
#A
そして、左上と右下を'.'に置き換えます。
..
#.
これもまた、この問題の入力の一つとしてありえます。
このように、左上と右下が'.'のグリッドグラフ上をstackを持ちながら移動する問題だととらえると、再帰的に同じ問題が現れます。
これはメモ化再帰チャンスですね。
左上と右下のペアの数は、26*10*10くらいです。
ある左上と右下のペアについてこの問題を解いているとき、その内部にある別のペアたちを組み合わせて実際のパスを作っていくことになります。
これをいい感じにやるために、内部でdpをします。「グリッドグラフ上で左または下にのみ動ける問題」でよく見られる二次元dpをやります(左または下に配る)。
ただ、再帰的な問題が現れたときのみ、遠くにも配る感じです。
うまく説明できないのでこれで終わりにします。
コードの方もごちゃごちゃしていて汚いので(特にpairの中にpairを入れていてfirstとsecondが乱発されているあたり)、あてにしないほうがいいと思います。
考察しているときもすごく楽しくて、とても良問だなあと思いました。ただ、実装でバグを埋めて死んだのでもうちょっと全体をとらえながら実装する力が欲しい
