問題説明

N×Mサイズの部屋にロボット掃除機があります。 ロボットは次のルールで動きます: 1. 現在のマスが掃除されていなければ掃除する。 2. 現在の方向を基準に左から探索: - 左に掃除していない空きマスがあれば回転して前進 - なければ左に回転し続ける 3. 4方向全て掃除済みか壁なら: - 後退可能なら後退して2番へ - 後退不可(壁)なら作動終了 ロボットが掃除するマスの数を求めてください。

入力

出力

制約条件

• •3 <= N, M <= 50
• •方向 d: 0(北), 1(東), 2(南), 3(西)
• •最初のロボット位置は常に空き

例

3 3
1 1 0
1 1 1
1 0 1
1 1 1

1

4 4
1 1 0
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

4