グリッドから出ずにいられるか？
コンピュータゲームを設計するとき、h-by-w のグリッドを使うことがあります。各セルには、<>v^ のいずれかの矢印記号が設定されていて、そのセルに到達したときは記号が示す方向へ移動しなければなりません。
スタート地点はランダムなセルですが、そこに書かれている方向へ進むことで、グリッドの外に出てしまう場合があります。そうなったらゲームオーバーです。
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
ゲームの設計者としては、一度スタートするとずっとグリッド内に留まるようなセルができるだけ多いほうが望ましいですよね。そこで、「どのセルからスタートすると常にグリッド内に留まれるか」を調べたいと考えています。最終的には、常にグリッド上で動き続けられるセルの数を求めたいわけです。
Input
入力の最初の行には、2 つの整数 h と w (1 ≤ h, w ≤ 1000) が与えられます。
続く h 行には、各セルが示す移動方向 (<>v^) を表す文字がそれぞれ w 文字ずつ与えられます。
Output
常にグリッドの外に出ずに動き続けられるセルの数を出力してください。
Examples
Input | Output |
|---|---|
4 5 | 14 |
Explanation
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB