Palindrome Generator (AOJ 2307)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2307

問題

頂点数n、辺数mの有向グラフが与えられる。各頂点には文字列が書かれている。グラフをwalkしたときに訪れた頂点の順番で文字列を連結した物を考える。そうしてできた文字列で回文になっているものの最大の長さを答えよ。
1<=n<=100
1<=m<=1000
各頂点の文字列の長さ<=10

解法

いま見ている左端の頂点、右端の頂点、その頂点で使った文字数、どちらの頂点で文字が残っているかでメモ化再帰。中央の頂点での回文の判定もメモ化した。文字列が無限に伸びるかどうかの判定は、dfs中にその頂点に初めて訪れたら1を立て、2回目に訪れたら2を立てるようにして、returnする直前で返り値が0以上で2が立っていたら無限大を返すようにした。