SRM651 div1 250

問題

W*Hマスのボードが与えられる。
各マスは、空か、スタート位置か、壁か、の三通りが与えられている。
今、ロボットがスタート地点から上下左右の組み合わせのコマンドによって動くが、以下のような挙動をする。
・コマンドに従い動いて、動く先が空マスならそのマスに移動
・コマンドに従い動いて、動く先が壁なら今のマスにとどまる
・コマンドに従い動いて、ボードから外に出たら即座に停止

今、コマンドをロボットに送信するが、通信によって一部のコマンドが消えてなくなる(部分列になる)。
このような場合、コマンドのどの部分列を取ってもボードから外に出ないようなコマンドのうち、一番長いコマンドの長さを返す。
もし無限に長いコマンドが作れる場合は-1を返す。

W,H<=50

考え方

スタート地点から上下左右のどれか一直線上に壁がある場合は、UUUUU...のように同じコマンドで無限に長いコマンドが作れる。

そうでない場合、壁に当たりに行こうとするコマンドの部分が消えてしまうとそうでないコマンドの残りの部分でボードから出ないようになっていないと、落ちてしまう。
なので、結局、壁に当たりに行くようなコマンドは使えないので、落ちないようなコマンドが最長になる。
スタート地点からボードを落ちないようなコマンドは、上方向に落ちないマス数＋下方向に落ちないマス数＋右方向に落ちないマス数＋左方向に落ちないマス数になるので、結局W-1+H-1が答えになる。