Problem
エリックは大学で警備員として働いているので、一日の仕事が終わると建物の周りを歩き回り、夜は電気を消します
。
建物はn階建てで、階段は左右に2つずつあります。左右の階段を繋ぐ廊下沿いに各階にm部屋あります。言い換えれば、建物は n 行、m + 2 列の長方形として表すことができます。ここで、最初と最後の列は —階段があり、真ん中に m 個の列があります。部屋
など。
エリックは今、1 階の左側の階段に立っています。彼はどこの照明も消したいと考えていますが、現在のフロアのすべての照明を消す前に上の階に上がることはしたくありません。もちろん、電気を消すにはエリックが部屋にいなければなりません。エリックは、1 つのフロアの階段を上る、または同じフロアの次の部屋または階段から次の部屋または階段に移動するのに 1 分間かかります。エリックがいる部屋の電気を消すのに時間はかかりません。
エリックが建物内のすべての照明を消す最小限の時間を見つけるのを手伝ってください。
なお、エリックは元の位置に戻る必要はなく、また、すでに消灯している部屋を訪問する必要もありません
。
入力:
最初の行には、2 つの整数 n と m (1<<n ≤ 15、1<le; m ≤ 100) が含まれています。階数と各階の部屋数
をそれぞれ表示します。
次の n 行には建物の説明が含まれます。各行には、1 つのフロア (左の階段、次に m の部屋、次に右の階段) を表す 0 と長さ m + 2 の文字列が含まれます。0 は照明がオフであることを意味し、1 は照明がオンであることを意味します。階は上から下の順に記載されており、特に最後の行は1階について説明しています
。
各行の最初と最後の文字は階段を表すので常に0になります。
出力:
数字を 1 つ出力します。すべての照明を消すのに必要な最小限の時間
です。
例:
<本体>
| 入力 |
出力 |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
説明:
最初の例では、エリックはまず 1 階の部屋 1 に行き、次に —はしごを使用して 2 階の Room 2 に移動します。
2 番目の例では、最初に 1 階の 4 番目の部屋に行き、右側の階段で 1 階上に上がり、2 階の 4 番目の部屋に入り、再び右側の階段を上って、2 番目の部屋に進みます。最上階の部屋。