B - Dangerous Areas Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君の町は縦 H 行、横 W 列の区域に分かれています。町の様子は H 個の文字列 S_1, S_2, \ldots, S_H で表され、 S_i の j 文字目は上から i 行目、左から j 列目の区域の様子です。 X は危険な区域であることを、 . は安全な区域であることを表します。

高橋君は上の行から順に見ていき、危険な区域が 1 つ以上含まれる行を最初に見つけたところで調査を始めます。調査を始める行は上から何行目かを求めてください。危険な区域が 1 つもない場合は -1 を出力してください。

制約

  • 1 \leq H \leq 10
  • 1 \leq W \leq 10
  • S_i は X と . のみからなる長さ W の文字列

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
S_2
\vdots
S_H
  • 1 行目には、町の行数 H と列数 W がスペース区切りで与えられる。
  • 2 行目から H 行にわたり、 1 + i 行目には上から i 行目の様子を表す文字列 S_i が与えられる。

出力

調査を始める行が上から何行目かを 1 行で出力せよ。危険な区域がない場合は -1 を出力せよ。

入力例 1

3 4
....
..X.
....

出力例 1

2

入力例 2

2 3
...
...

出力例 2

-1

入力例 3

2 2
X.
..

出力例 3

1

入力例 4

5 2
..
..
..
.X
..

出力例 4

4

入力例 5

7 2
..
..
.X
..
..
..
..

出力例 5

3

Score : 233 pts

Problem Statement

Takahashi's town is divided into areas arranged in H rows and W columns. The state of the town is represented by H strings S_1, S_2, \ldots, S_H, where the j-th character of S_i describes the area in the i-th row from the top and the j-th column from the left. X denotes a dangerous area, and . denotes a safe area.

Takahashi examines the rows from top to bottom and begins his investigation at the first row he finds that contains one or more dangerous areas. Determine which row from the top he starts investigating. If there is no dangerous area at all, print -1.

Constraints

  • 1 \leq H \leq 10
  • 1 \leq W \leq 10
  • S_i is a string of length W consisting only of X and ..

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H
  • The first line contains the number of rows H and the number of columns W, separated by a space.
  • The following H lines describe the rows: the (1 + i)-th line contains the string S_i representing the state of the i-th row from the top.

Output

Print, on a single line, which row from the top Takahashi starts investigating. If there is no dangerous area, print -1.

Sample Input 1

3 4
....
..X.
....

Sample Output 1

2

Sample Input 2

2 3
...
...

Sample Output 2

-1

Sample Input 3

2 2
X.
..

Sample Output 3

1

Sample Input 4

5 2
..
..
..
.X
..

Sample Output 4

4

Sample Input 5

7 2
..
..
.X
..
..
..
..

Sample Output 5

3