2x2 Erasing

AtCoder

IDarc205_a

Time2000ms

Memory256MB

Difficulty—

There is a grid with $N$ rows and $N$ columns. Let $(r,c)$ denote the cell at the $r$\-th row from the top and $c$\-th column from the left. Each cell is colored black or white. Cell $(r,c)$ is colored black when $S_{r,c}$ is `#`, and white when $S_{r,c}$ is `.`. You are given $Q$ questions about this grid, so answer each of them. In the $i$\-th question $(1\le i\le Q)$, integers $U_i,D_i,L_i,R_i$ are given, so find the answer to the following question. * After coloring all cells that do **not** satisfy $U_i \le r \le D_i$ and $L_i \le c \le R_i$ black, find the maximum number of times you can perform the following operation. * Choose a pair of integers $(r,c)$ such that cells $(r,c),(r,c+1),(r+1,c),(r+1,c+1)$ are all colored white, and color one of these four cells black. Solve each question independently. In other words, the color of each cell is reset to the initial state for each question. ## Constraints * $2\le N\le 500$ * $1\le Q\le 2\times 10^5$ * $S_{r,c}$ is `.` or `#`. * $1\le U_i < D_i \le N$ * $1\le L_i < R_i \le N$ * $N,Q,U_i,D_i,L_i,R_i$ are all integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $S_{1,1}S_{1,2}\ldots S_{1,N}$ $S_{2,1}S_{2,2}\ldots S_{2,N}$ $\vdots$ $S_{N,1}S_{N,2}\ldots S_{N,N}$ $U_1$ $D_1$ $L_1$ $R_1$ $U_2$ $D_2$ $L_2$ $R_2$ $\vdots$ $U_Q$ $D_Q$ $L_Q$ $R_Q$ [samples]

Samples

Input #1

5 4
..#.#
.....
#....
...#.
.#...
1 3 1 3
3 5 3 5
2 3 1 4
1 5 1 5

Output #1

2
0
2
5

Consider the first question.
After coloring all cells that do not satisfy $1\le r\le 3$ and $1\le c\le 3$ black, the grid becomes as follows.

..###
...##
#..##
#####
#####

You can perform the operation twice on this grid as follows.

*   Choose $(r,c)=(1,1)$. Among cells $(1,1),(1,2),(2,1),(2,2)$, choose cell $(1,2)$ and color it black.
*   Choose $(r,c)=(2,2)$. Among cells $(2,2),(2,3),(3,2),(3,3)$, choose cell $(2,2)$ and color it black.

You cannot perform the operation more than twice, so output $2$ on the first line.

Input #2

7 6
#.#....
.....#.
.......
.#..#.#
#....#.
.......
....##.
1 3 2 7
4 6 1 6
6 7 2 7
3 5 4 6
1 6 2 4
1 7 1 7

Output #2

API Response (JSON)

{
  "problem": {
    "name": "2x2 Erasing",
    "description": {
      "content": "There is a grid with $N$ rows and $N$ columns. Let $(r,c)$ denote the cell at the $r$\\-th row from the top and $c$\\-th column from the left. Each cell is colored black or white. Cell $(r,c)$ is colore",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc205_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a grid with $N$ rows and $N$ columns. Let $(r,c)$ denote the cell at the $r$\\-th row from the top and $c$\\-th column from the left. Each cell is colored black or white. Cell $(r,c)$ is colore...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments