B - あみだくじ Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君は学校で班のリーダーを決めなければいけなくなったので、あみだくじを用いて決めることにしました。
　あみだくじとは、複数の縦線から 1 本を選び、その上端から下端へと辿っていき、途中で横線があれば、その横線を通り繋がっている隣接する縦線へと移動し、また下へと進みます。
　今日はたまたま手元に紙がなかったので、パソコン上で |、-、o を用いて以下のようなあみだくじを作りました。
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
            o
　o がある位置に到達した人がリーダーになります。
　実は高橋君はリーダーになりたかったので、どの縦線を選べば o に辿り着くのか知りたいです。

　左から何番目の縦線を選べばリーダーになれるのかを求めなさい。

入力

入力は以下の形式で標準入力から与えられる。 
N L
|x|x|‥‥|
|x|x|‥‥|
|x|x|‥‥|
: : :  :
: : :  :
| | |‥‥|
y y y‥‥y
  • 入力は L+2 行ある。
  • 1 行目には、あみだくじの縦線の本数を表す整数 N(1≦N≦10) とあみたくじの長さを表す整数 L(1≦L≦20)が与えられる。
  • 2 行目からの L 行には、あみたくじの形が与えられる。
    • i 行目 (2≦i≦L+1) には 2N-1 文字の記号が与えられる。
    • 各行の j 番目の記号は、以下のようになっている。
      • j が奇数の時：|
      • j が偶数の時(上記のxの位置)：- または (空白)
    • | はあみだくじの縦線を表し、-はその両端の縦線を繋ぐ横線であることを表す。また、空白はその位置に横線が無いことを表す。
    • | を 1 つ挟んで左右に隣り合ったxの位置の両方が - という入力は存在しない。
  • L+2 行目には 2N-1 文字の記号が与えられる。
    • 各行の j 番目の記号は、以下のようになっている。
      • j が奇数の時(上記のyの位置)：o または (空白)
      • j が偶数の時： (空白)
    • o は L+2 行目にただ 1 つのみ与えられる。

出力

あみだくじを辿って o に到達するために選ぶべき縦線は左から何番目か 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

3 2
| |-|
|-| |
o

出力例 1

3
  • 一番右の縦線を選ぶと、再左端に到達する。つまり、左から 3 番目を選択すると、 o のある位置に到達できる。

入力例 2

10 2
| |-| |-| |-| |-| |
|-| |-| |-| |-| |-|
            o

出力例 2

9
  • 左から 9 番目の縦線から辿ると、o の位置に到達できる。
  • したがって、答えは 9 になる。

入力例 3

1 5
|
|
|
|
|
o

出力例 3

1
  • 縦線が 1 本なので、左から 1 番目の縦線が答えとなる。

入力例 4

4 2
| | | |
| | | |
      o

出力例 4

4
  • 横線が 1 本も存在しないので、o のある縦線を選べば良い。
  • したがって左から 4 番目の縦線が答えとなる。

入力例 5

9 8
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
            o

出力例 5

3

Source Name

ARC 006