A - 2x2 Erasing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

縦 N 行、横 N 列のグリッドがあります。上から r 行目、左から c 列目のマスをマス (r,c) と表します。各マスは黒か白で塗られており、マス (r,c) は S_{r,c} が # のとき黒で、 S_{r,c} が . のとき白で塗られています。

このグリッドに対して Q 個の質問が与えられるので、それぞれについて答えを求めてください。 i 番目 (1\le i\le Q) の質問では整数 U_i,D_i,L_i,R_i が与えられるので、以下の質問の答えを求めてください。

  • U_i \le r \le D_i かつ L_i \le c \le R_i を 満たさない マスを全て黒で塗った後、以下の操作を最大で何回できるか求めてください。
    • マス (r,c),(r,c+1),(r+1,c),(r+1,c+1) が全て白で塗られているような整数の組 (r,c) を選び、これら 4 つのマスのうち 1 つを黒で塗る。

各質問について独立に解いてください。言い換えると、各マスの色は質問のたびにはじめの状態にリセットされます。

制約

  • 2\le N\le 500
  • 1\le Q\le 2\times 10^5
  • S_{r,c} は . または #
  • 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 は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

Q 行出力せよ。

i 行目 (1\le i\le Q) には、 i 番目の質問に対する答えを出力せよ。

入力例 1

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

出力例 1

2
0
2
5

1 番目の質問について考えます。

1\le r\le 3 かつ 1\le c\le 3 を満たさないようなマスを全て黒で塗ると、グリッドは以下のようになります。

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

このグリッドに対して以下のように 2 回操作を行うことができます。

  • (r,c)=(1,1) を選ぶ。マス (1,1),(1,2),(2,1),(2,2) の中からマス (1,2) を選び、黒で塗る。
  • (r,c)=(2,2) を選ぶ。マス (2,2),(2,3),(3,2),(3,3) の中からマス (2,2) を選び、黒で塗る。

2 回より多く操作をすることはできないので、 1 行目には 2 を出力してください。

入力例 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

出力例 2

4
4
2
0
6
13

Score : 400 points

Problem Statement

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

Output

Output Q lines.

The i-th line (1\le i\le Q) should contain the answer to the i-th question.

Sample Input 1

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

Sample 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.

Sample 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

Sample Output 2

4
4
2
0
6
13