A - Treasure Map Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、古い宝の地図を手に入れました。

地図には N 行 M 列のグリッド状の区画が描かれており、いくつかのマスには宝が埋まっている印が付いています。

高橋君は、宝が埋まっているすべてのマスを含むような長方形の領域を選び、その中を調査しようとしています。ここで長方形の領域とは、ある連続する行の範囲（上から r_1 行目から r_2 行目まで、r_1 \leq r_2）と、ある連続する列の範囲（左から c_1 列目から c_2 列目まで、c_1 \leq c_2）によって定まる、その両方の範囲に含まれるすべてのマスからなる領域のことです。この領域に含まれるマスの数は (r_2 - r_1 + 1) \times (c_2 - c_1 + 1) 個です。r_1 = r_2 かつ c_1 = c_2 の場合（マス 1 つだけからなる領域）も長方形の領域に含まれます。

調査の手間を最小限にするため、高橋君は、宝が埋まっているすべてのマスを含む長方形の領域のうち、含まれるマスの数が最小となるものを求めたいです。

条件を満たす長方形領域に含まれるマスの数の最小値を求めてください。

制約

  • 1 \leq N \leq 1000
  • 1 \leq M \leq 1000
  • N, M は整数
  • S_i（1 \leq i \leq N）は . と # からなる長さ M の文字列であり、地図の上から i 行目の状態を表す
  • # は全体で少なくとも 1 つ存在する

入力

N M
S_1
S_2
\vdots
S_N
  • 1 行目には、地図の行数を表す整数 N と列数を表す整数 M が、スペース区切りで与えられる。
  • 続く N 行にわたって、地図の各行の状態を表す長さ M の文字列 S_i が与えられる。
  • S_i の j 文字目が # のとき、上から i 行目・左から j 列目のマスに宝が埋まっていることを表す。
  • S_i の j 文字目が . のとき、そのマスには宝が埋まっていないことを表す。

出力

宝があるすべてのマスを含む長方形領域に含まれるマスの数の最小値を 1 行で出力せよ。

入力例 1

3 4
....
.##.
.#..

出力例 1

4

入力例 2

5 6
......
.#....
......
....#.
......

出力例 2

12

入力例 3

8 10
..........
..#.......
..........
..........
.......#..
..........
..#.......
..........

出力例 3

36

Score : 266 pts

Problem Statement

Takahashi has obtained an old treasure map.

The map depicts a grid of N rows and M columns, and some cells are marked with signs indicating that treasure is buried there.

Takahashi wants to select a rectangular region that contains all cells where treasure is buried, and investigate the area within it. Here, a rectangular region is defined by a contiguous range of rows (from the r_1-th row to the r_2-th row from the top, where r_1 \leq r_2) and a contiguous range of columns (from the c_1-th column to the c_2-th column from the left, where c_1 \leq c_2), consisting of all cells that fall within both ranges. The number of cells contained in this region is (r_2 - r_1 + 1) \times (c_2 - c_1 + 1). A region consisting of just a single cell (when r_1 = r_2 and c_1 = c_2) is also considered a rectangular region.

To minimize the effort of investigation, Takahashi wants to find, among all rectangular regions that contain every cell where treasure is buried, the one with the minimum number of cells.

Find the minimum number of cells contained in a rectangular region that satisfies the condition.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq M \leq 1000
  • N, M are integers
  • S_i (1 \leq i \leq N) is a string of length M consisting of . and #, representing the state of the i-th row from the top of the map
  • There is at least one # in total

Input

N M
S_1
S_2
\vdots
S_N
  • The first line contains an integer N representing the number of rows and an integer M representing the number of columns of the map, separated by a space.
  • Over the following N lines, a string S_i of length M representing the state of each row of the map is given.
  • If the j-th character of S_i is #, it indicates that treasure is buried in the cell at the i-th row from the top and the j-th column from the left.
  • If the j-th character of S_i is ., it indicates that no treasure is buried in that cell.

Output

Print on one line the minimum number of cells contained in a rectangular region that includes all cells where treasure is buried.

Sample Input 1

3 4
....
.##.
.#..

Sample Output 1

4

Sample Input 2

5 6
......
.#....
......
....#.
......

Sample Output 2

12

Sample Input 3

8 10
..........
..#.......
..........
..........
.......#..
..........
..#.......
..........

Sample Output 3

36