/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 H 行、横 W 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。
マス (i,j) は S_{i,j}= # のとき障害物が置かれており、S_{i,j}= . のとき何も置かれていません。
高橋君はグリッド内にいくつか監視カメラを設置しようとしています。
監視カメラは障害物のないマスに上下左右の 4 方向のいずれかの向きで置くことができます。
1 つのマスに複数台の監視カメラを設置することも可能です。
各監視カメラは、監視カメラの置かれたマス、及び、監視カメラの向いている向きにある直線上のマスを、障害物に遮られない範囲で監視することができます。
障害物の置かれていない全てのマスを監視するためには、最小でいくつの監視カメラを設置する必要がありますか？
制約
- 1 \leq H,W \leq 300
- S_{i,j} は
.または#である
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}\ldots S_{1,W}
\vdots
S_{H,1}\ldots S_{H,W}
出力
答えを出力せよ。
入力例 1
3 3 ... .#. ...
出力例 1
4
例えば、マス (1,1) に右向きと下向き、マス (3,3) に上向きと左向きの合計 4 台の監視カメラを設置すると、障害物の置かれていない全てのマスを監視することができます。
入力例 2
3 5 ...## .#... ...#.
出力例 2
5
例えば、マス (1,1) に右向きと下向き、マス (3,3) に左向き、マス (2,5) に左向きと下向きの合計 5 台の監視カメラを設置すると、障害物の置かれていない全てのマスを監視することができます。
マス (2,5) に左向きに設置したカメラは、マス (2,2) の障害物に遮られるため、マス (2,1) を監視できないことに注意してください。
入力例 3
14 107 ........................................................................................................... ........................................................................................................... ..#########..###....###########..###.......###...###########..####.......###...###########...###########... ..########..###....###########....###.....###...###########...#####......###..###########...###########.... ..#######..###.....###.............###...###....###...........######.....###..###...........###............ ..######..###......###..............###.###.....###...........###.###....###..###...........###............ ..#####..###.......############......#####......############..###..###...###..###...........############... ..####....###......############.......###.......############..###...###..###..###...........############... ..###......###.....###................###.......###...........###....###.###..###...........###............ ..##........###....###................###.......###...........###.....######..###...........###............ ..#..........###...############.......###.......############..###......#####..############..############... ..............###...###########.......###........###########..###.......####...###########...###########... ........................................................................................................... ...........................................................................................................
出力例 3
91
Score : 600 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Square (i, j) is occupied by an obstacle if S_{i,j}= #, and is empty if S_{i,j}= ..
Takahashi will install some surveillance cameras in the grid.
A surveillance camera can be placed at a square without an obstacle, in one of the four directions: up, down, left, or right.
Multiple surveillance cameras may be placed at the same square.
Each surveillance camera monitors the square it is placed at, and the squares in the direction it is placed in, as far as there is no obstacle in between.
At least how many surveillance cameras are needed to monitor all squares without an obstacle?
Constraints
- 1 \leq H,W \leq 300
- S_{i,j} is
.or#.
Input
The input is given from Standard Input in the following format:
H W
S_{1,1}\ldots S_{1,W}
\vdots
S_{H,1}\ldots S_{H,W}
Output
Print the answer.
Sample Input 1
3 3 ... .#. ...
Sample Output 1
4
For example, if we install two surveillance cameras at square (1, 1) facing right and down, and another two at square (3, 3) facing up and left, all squares without an obstacle will be monitored.
Sample Input 2
3 5 ...## .#... ...#.
Sample Output 2
5
For example, if we install two surveillance cameras at square (1, 1) facing right and down, another at square (3, 3) facing left, and another two at square (2, 5) facing left and down, all squares without an obstacle will be monitored.
Note that the camera at square (2, 5) facing left cannot monitor square (2, 1), since there is an obstacle in between at square (2, 2).
Sample Input 3
14 107 ........................................................................................................... ........................................................................................................... ..#########..###....###########..###.......###...###########..####.......###...###########...###########... ..########..###....###########....###.....###...###########...#####......###..###########...###########.... ..#######..###.....###.............###...###....###...........######.....###..###...........###............ ..######..###......###..............###.###.....###...........###.###....###..###...........###............ ..#####..###.......############......#####......############..###..###...###..###...........############... ..####....###......############.......###.......############..###...###..###..###...........############... ..###......###.....###................###.......###...........###....###.###..###...........###............ ..##........###....###................###.......###...........###.....######..###...........###............ ..#..........###...############.......###.......############..###......#####..############..############... ..............###...###########.......###........###########..###.......####...###########...###########... ........................................................................................................... ...........................................................................................................
Sample Output 3
91