Security Camera 3

AtCoder

IDabc274_g

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

3 3
...
.#.
...

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.

Input #2

3 5
...##
.#...
...#.

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)$.

Input #3

14 107
...........................................................................................................
...........................................................................................................
..#########..###....###########..###.......###...###########..####.......###...###########...###########...
..########..###....###########....###.....###...###########...#####......###..###########...###########....
..#######..###.....###.............###...###....###...........######.....###..###...........###............
..######..###......###..............###.###.....###...........###.###....###..###...........###............
..#####..###.......############......#####......############..###..###...###..###...........############...
..####....###......############.......###.......############..###...###..###..###...........############...
..###......###.....###................###.......###...........###....###.###..###...........###............
..##........###....###................###.......###...........###.....######..###...........###............
..#..........###...############.......###.......############..###......#####..############..############...
..............###...###########.......###........###########..###.......####...###########...###########...
...........................................................................................................
...........................................................................................................

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Security Camera 3",
    "description": {
      "content": "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)$ ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc274_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.  \nSquare $(i, j)$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments