C - Digital Graffiti Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

H 行 W 列のマス目があります。このマス目の、上から i 番目、左から j 番目のマスを、マス (i, j) と呼ぶことにします。
各マスは黒または白に塗られています。S_{i, j} が # ならばマス (i, j) は黒に塗られており、. ならば白に塗られています。
マス目の一番外側のマス、すなわち (1, j), (H, j), (i, 1), (i, W) のいずれかの形で表されるマスは白に塗られていることが保証されます。

黒に塗られた部分を多角形として見たとき、これが (最小で) 何角形になるかを求めてください。

ここで、黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。すなわち、以下のことが保証されます。

  • 黒に塗られたマスが少なくとも一つ存在する
  • 黒に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である
  • 白に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)

制約

  • 3 \le H \le 10
  • 3 \le W \le 10
  • S_{i, j} は # または .
  • S_{1, j}, S_{H, j} は .
  • S_{i, 1}, S_{i, W} は .
  • 黒に塗られた部分は一つの自己交叉のない多角形となる

入力

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

H W
S_{1, 1} S_{1, 2} S_{1, 3} \dots S_{1, W}
S_{2, 1} S_{2, 2} S_{2, 3} \dots S_{2, W}
S_{3, 1} S_{3, 2} S_{3, 3} \dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1} S_{H, 2} S_{H, 3} \dots S_{H, W}

出力

黒に塗られた部分を n 角形として見ることができるような最小の n を出力せよ。

入力例 1

5 5
.....
.###.
.###.
.###.
.....

出力例 1

4

マス目の左上、左下、右上、右下の隅をそれぞれ (0, 0), (H, 0), (0, W), (H, W) とする座標系で表すと、与えられる図形は (1, 1), (4, 1), (4, 4), (1, 4) を頂点とする 4 角形です。

Score : 300 points

Problem Statement

We have a grid with H rows and W columns. Let (i, j) be the square at the i-th row from the top and j-th column from the left.
Each square is painted black or white. If S_{i, j} is #, (i, j) is painted black; if S_{i, j} is ., (i, j) is painted white.
It is guaranteed that the outermost squares are white. That is, the squares that can be represented as (1, j), (H, j), (i, 1), or (i, W) are white.

Consider the part of the grid that is painted black as a polygon. How many sides does it have (at least)?

Here, it is guaranteed that the part painted black forms a polygon without self-intersection, that is, the following holds:

  • at least one square is painted black;
  • we can travel between any two squares painted black by repeatedly moving up, down, left, or right while going through only black squares;
  • we can travel between any two squares painted white by repeatedly moving up, down, left, or right while going through only white squares. (Note that the outermost squares in the grid are all painted white.)

Constraints

  • 3 \le H \le 10
  • 3 \le W \le 10
  • S_{i, j} is # or ..
  • S_{1, j} and S_{H, j} are ..
  • S_{i, 1} and S_{i, W} are ..
  • The part painted black forms a polygon without self-intersection.

Input

Input is given from Standard Input in the following format:

H W
S_{1, 1} S_{1, 2} S_{1, 3} \dots S_{1, W}
S_{2, 1} S_{2, 2} S_{2, 3} \dots S_{2, W}
S_{3, 1} S_{3, 2} S_{3, 3} \dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1} S_{H, 2} S_{H, 3} \dots S_{H, W}

Output

Print the minimum number n such that the part painted black can be seen as an n-gon.

Sample Input 1

5 5
.....
.###.
.###.
.###.
.....

Sample Output 1

4

If we use a coordinate system where the top-left, bottom-left, top-right, and bottom-right corners of the grid are (0, 0), (H, 0), (0, W), and (H, W), the given figure is a quadrilateral whose vertices are (1, 1), (4, 1), (4, 4), and (1, 4).