/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 425 点
問題文
H 行 W 列のマス目があり、いくつか（0 個のこともある）のマスには磁石が置かれています。
マス目の状態は H 個の 長さ W の文字列 S_1,S_2,\ldots,S_H で表され、
S_i の j 文字目が # のとき上から i 行目かつ左から j 列目のマスには磁石が置かれていることを、
. のとき何も置かれていないことを表しています。
高橋君は鉄の鎧を着ており、あるマスにいるとき次のように移動することができます。
- 現在いるマスの上下左右に隣り合うマスのいずれかに磁石が置かれているとき、どこへも移動することができない。
- そうでないとき、上下左右に隣り合うマスのいずれかを選んでそのマスに移動することができる。
ただし、マス目の外に移動することはできない。
磁石が置かれていない各マスについて、そのマスの自由度を、「最初高橋くんがそのマスにいるとき、そこから移動を繰り返して到達できるマスの個数」として定義します。 マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を求めてください。
ただし、自由度の定義において、「移動を繰り返して到達できるマス」とは、最初にいるマスからそのマスまで移動を繰り返して到達する方法（1 回も移動しないものも含む）が 1 つ以上存在するようなマスのことであり、 最初のマスから始めてすべてのそのようなマスを巡るような移動方法が存在する必要はありません。特に（磁石の置かれていない）各マス自身は、そのマスから「移動を繰り返して到達できるマス」につねに含まれることに注意してください。
制約
- 1\leq H,W\leq 1000
- H,W は整数
- S_i は
.と#のみからなる長さ W の文字列 - 磁石の置かれていないマスが少なくとも 1 つ存在する。
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
マス目のうち磁石が置かれていないマスの中における、マスの自由度の最大値を出力せよ。
入力例 1
3 5 .#... ..... .#..#
出力例 1
9
上から i 行目かつ左から j 列目のマスを (i,j) で表します。 高橋君が最初に (2,3) にいるとき、高橋君の移動の例としては次のようなものなどが考えられます。
- (2,3)\to (2,4)\to (1,4)\to (1,5)\to (2,5)
- (2,3)\to (2,4)\to (3,4)
- (2,3)\to (2,2)
- (2,3)\to (1,3)
- (2,3)\to (3,3)
よって、途中で到達しているマスも含めて高橋君は (2,3) から少なくとも 9 個のマスに到達することができます。 一方、これら以外のマスには到達することができないため、(2,3) の自由度は 9 となります。
これは磁石が置かれていない各マスの自由度のうち最大であるため、9 を出力します。
入力例 2
3 3 ..# #.. ..#
出力例 2
1
磁石が置かれていないどのマスについても、上下左右に隣り合うマスのいずれかに磁石が置かれています。
よって、磁石が置かれていないどのマスからも移動することはできず、マスの自由度は 1 となります。
そのため、1 を出力します。
Score: 425 points
Problem Statement
There is a grid of H rows and W columns. Some cells (possibly zero) contain magnets.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H of length W. If the j-th character of S_i is #, it indicates that there is a magnet in the cell at the i-th row from the top and j-th column from the left; if it is ., it indicates that the cell is empty.
Takahashi, wearing an iron armor, can move in the grid as follows:
- If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
- Otherwise, he can move to any one of the vertically or horizontally adjacent cells.
However, he cannot exit the grid.
For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.
Here, in the definition of degree of freedom, "cells he can reach by repeatedly moving" mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.
Constraints
- 1 \leq H, W \leq 1000
- H and W are integers.
- S_i is a string of length W consisting of
.and#. - There is at least one cell without a magnet.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the maximum degree of freedom among all cells without magnets.
Sample Input 1
3 5 .#... ..... .#..#
Sample Output 1
9
Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. If Takahashi starts at (2,3), possible movements include:
- (2,3) \to (2,4) \to (1,4) \to (1,5) \to (2,5)
- (2,3) \to (2,4) \to (3,4)
- (2,3) \to (2,2)
- (2,3) \to (1,3)
- (2,3) \to (3,3)
Thus, including the cells he passes through, he can reach at least nine cells from (2,3).
Actually, no other cells can be reached, so the degree of freedom for (2,3) is 9.
This is the maximum degree of freedom among all cells without magnets, so print 9.
Sample Input 2
3 3 ..# #.. ..#
Sample Output 2
1
For any cell without a magnet, there is a magnet in at least one of the adjacent cells.
Thus, he cannot move from any of these cells, so their degrees of freedom are 1.
Therefore, print 1.