← 返回题目列表

AtCoder · arc205_a

A. 2x2 擦除

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个网格 N 行和 N 列。让 (r,c) 表示位于 r从顶部数第行和 c左起第 列。每个单元格的颜色都是黑色或白色。细胞 (r,c) 为黑色时 S_{r,c} is #,并且白色时 S_{r,c} is ..

你被给予 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),(r,c+1),(r+1,c),(r+1,c+1) 全部涂成白色,并将这四个单元格之一涂成黑色。

独立解决每个问题。换句话说,每个问题的每个单元格的颜色都会重置为初始状态。

约束

  • 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 均为整数。

输入

输入由标准输入按以下格式给出:

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\le r\le 3 和 1\le c\le 3 黑色,网格变成如下。

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

您可以在此网格上执行两次操作,如下所示。

  • 选择 (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 在第一行。


示例输入 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