/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は美術館の管理人をしています。美術館の壁には H 行 W 列のグリッド状にタイルが並んでおり、各タイルは一辺の長さが 1 の正方形です。上から i 行目、左から j 列目のタイルを (i, j) と表します。
各タイルは絵画の一部であるタイル（# で表す）か、何も描かれていない空白のタイル（. で表す）のいずれかです。
高橋君は、すべての絵画タイルを含むような、グリッドの行・列に沿った長方形の額縁を設置したいと考えています。具体的には、ある整数 r_1, r_2, c_1, c_2（1 \leq r_1 \leq r_2 \leq H, 1 \leq c_1 \leq c_2 \leq W）を選び、(r_1, c_1) を左上隅、(r_2, c_2) を右下隅とする長方形のタイル領域を定めます。すべての絵画タイルはこの長方形領域に含まれていなければなりません。すなわち、絵画タイル (i, j) が存在するならば、r_1 \leq i \leq r_2 かつ c_1 \leq j \leq c_2 を満たす必要があります。
この長方形領域は、縦に h = r_2 - r_1 + 1 タイル、横に w = c_2 - c_1 + 1 タイルを含みます。各タイルの一辺の長さは 1 なので、この長方形領域の縦の長さは h、横の長さは w であり、その周の長さは 2 \times (h + w) です。
高橋君は、すべての絵画タイルを含む長方形領域のうち、周の長さが最小となるものを求めたいと考えています。その最小の周の長さを出力してください。
ただし、絵画タイルが 1 つも存在しない場合は、額縁を設置する必要がないため 0 を出力してください。
制約
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W は整数
- S_i（1 \leq i \leq H）は
#と.からなる長さ W の文字列である
入力
H W S_1 S_2 \vdots S_H
- 1 行目には、グリッドの行数を表す整数 H と列数を表す整数 W が、スペース区切りで与えられる。
- 2 行目から H 行にわたって、グリッドの各行の情報を表す文字列 S_i が与えられる。
- 1 + i 行目（1 \leq i \leq H）には、i 行目のグリッド情報である長さ W の文字列 S_i が与えられる。S_i の j 文字目はタイル (i, j) の状態を表し、
#は絵画タイル、.は空白タイルを意味する。
出力
すべての絵画タイルを含む長方形領域のうち、周の長さの最小値を 1 行で出力せよ。絵画タイルが存在しない場合は 0 を出力せよ。
入力例 1
5 5 ..... .#.#. ..... .#.#. .....
出力例 1
12
入力例 2
3 4 .... .... ....
出力例 2
0
入力例 3
8 10 .......... #........# .......... ..#..#.... .......... ....##.... .......#.. ..........
出力例 3
32
Score : 233 pts
Problem Statement
Takahashi is a curator at an art museum. The museum wall has tiles arranged in a grid of H rows and W columns, where each tile is a square with side length 1. The tile at the i-th row from the top and the j-th column from the left is denoted as (i, j).
Each tile is either a painting tile (represented by #), which is part of a painting, or a blank tile (represented by .), on which nothing is drawn.
Takahashi wants to install a rectangular frame aligned with the grid's rows and columns that contains all painting tiles. Specifically, he chooses integers r_1, r_2, c_1, c_2 (1 \leq r_1 \leq r_2 \leq H, 1 \leq c_1 \leq c_2 \leq W) and defines a rectangular tile region with (r_1, c_1) as the top-left corner and (r_2, c_2) as the bottom-right corner. All painting tiles must be contained within this rectangular region. That is, if a painting tile (i, j) exists, then r_1 \leq i \leq r_2 and c_1 \leq j \leq c_2 must hold.
This rectangular region contains h = r_2 - r_1 + 1 tiles vertically and w = c_2 - c_1 + 1 tiles horizontally. Since each tile has side length 1, the vertical length of this rectangular region is h, the horizontal length is w, and its perimeter is 2 \times (h + w).
Takahashi wants to find, among all rectangular regions that contain all painting tiles, the one with the minimum perimeter. Output this minimum perimeter.
However, if there are no painting tiles, there is no need to install a frame, so output 0.
Constraints
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W are integers
- S_i (1 \leq i \leq H) is a string of length W consisting of
#and.
Input
H W S_1 S_2 \vdots S_H
- The first line contains integers H and W, representing the number of rows and columns of the grid, separated by a space.
- Over the next H lines, the string S_i representing each row of the grid is given.
- The (1 + i)-th line (1 \leq i \leq H) contains the string S_i of length W representing the grid information of the i-th row. The j-th character of S_i represents the state of tile (i, j), where
#denotes a painting tile and.denotes a blank tile.
Output
Output in a single line the minimum perimeter among all rectangular regions that contain all painting tiles. If there are no painting tiles, output 0.
Sample Input 1
5 5 ..... .#.#. ..... .#.#. .....
Sample Output 1
12
Sample Input 2
3 4 .... .... ....
Sample Output 2
0
Sample Input 3
8 10 .......... #........# .......... ..#..#.... .......... ....##.... .......#.. ..........
Sample Output 3
32