/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
縦 H 行、横 W 列のグリッドがあります。
上から i 行目左から j 列目のマスは S_{i,j} が # のとき黒く、 . のとき白く塗られています。
白マスからなる四方位に連結な領域のうち、黒マスに囲まれたものの個数を求めてください。
より厳密には次の通りです。
上から i 行目左から j 列目のマスをマス (i,j) と表します。
2 つのマス (i,j),(i',j') が隣接しているとは、|i-i'|+|j-j'|=1 であることと定めます。
白マスの集合 C が連結であるとは、C に属するどの 2 マス c,c' に対しても、C に属する隣接するマスへの移動を繰り返すことで c から c' へ移動できることと定めます。
空でない白マスの連結な集合であって、極大なものを白マスの連結成分と定めます。
白マスの連結成分であって、グリッドの最外周（すなわち、 1 行目、 H 行目、 1 列目、 W 行目）のマスを含まないものの個数を求めてください。
制約
- 3 \leq H,W \leq 10^3
- H,W は整数
- S_{i,j} は
#か.
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}S_{1,2}\dots S_{1,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
出力
答えを出力せよ。
入力例 1
5 15 ##########..### #...#######.### ####....###..## ######.######## ########....###
出力例 1
2
上から 2 行目左から 2,3,4 列目の 3 マスからなる領域と、上から 3 行目左から 5,6,7,8 列目及び上から 4 行目左から 7 列目の計 5 マスからなる領域の 2 個です。
入力例 2
10 22 ###################### ####.################# ###...################ ##.###.##.....######## ##.....##.####.####### .######.#......#.....# .######.#.####.#.##### #########.....##.##### ################.##### ################.....#
出力例 2
4
Score : 300 points
Problem Statement
There is a grid with H rows and W columns.
The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if S_{i,j} is ..
Among the four-directionally connected regions consisting of white cells, find the number of those that are surrounded by black cells.
Below is a more formal statement.
We denote the cell at the i-th row from the top and j-th column from the left as cell (i, j).
Two cells (i, j) and (i', j') are said to be adjacent if and only if |i-i'|+|j-j'|=1.
A set C of white cells is said to be connected if and only if, for any two cells c and c' in C, it is possible to move from c to c' by repeatedly moving to an adjacent cell in C.
A non-empty connected set of white cells that is maximal is called a connected component of white cells.
Find the number of connected components of white cells that do not contain any cell on the outermost border of the grid (that is, in row 1, row H, column 1, or column W).
Constraints
- 3 \leq H, W \leq 10^3
- H and W are integers.
- S_{i,j} is
#or..
Input
The input is given from Standard Input in the following format:
H W
S_{1,1}S_{1,2}\dots S_{1,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}
Output
Output the answer.
Sample Input 1
5 15 ##########..### #...#######.### ####....###..## ######.######## ########....###
Sample Output 1
2
There are two such regions: the region consisting of the three cells in row 2 from the top and columns 2, 3, 4 from the left, and the region consisting of a total of five cells: columns 5, 6, 7, 8 from the left in row 3 from the top and column 7 from the left in row 4 from the top.
Sample Input 2
10 22 ###################### ####.################# ###...################ ##.###.##.....######## ##.....##.####.####### .######.#......#.....# .######.#.####.#.##### #########.....##.##### ################.##### ################.....#
Sample Output 2
4