Luogu P1191 矩形

发表于 | 更新于 | 阅读次数：

题目描述

给出一个 $n \times n$ 的矩阵，矩阵中，有些格子被染成白色，有些格子被染成黑色，现要求矩阵中白色矩形的数量。

输入输出格式

输入格式：

第一行，一个整数 $n$ ，表示矩形的大小。

接下来 $n$ 行，每行 $n$ 个字符，这些字符为“$\rm W$”或“$\rm B}$”。其中“$\rm W}$”表示白格，“$\rm B$”表示黑格。

输出格式：

一个正整数，为白色矩形数量。

输入输出样例

输入样例#1：

1
2
3
4
5
4
WWBW
BBWB
WBWW
WBWB

输出样例#1：

1
15

说明

对于 $30\%$ 的数据，$n \leq 50$ ；

对于 $100\%$ 的数据，$n \leq 150$ ；

题解

写这道题的题解主要还是为了巩固一下二维前缀和。

为啥这题能用二维前缀和解呢，因为我们可以把这个矩阵看成一个 $01$ 矩阵。

$$\begin{matrix}\text{W}&\text{W}&\text{B}&\text{W}\\\text{B}&\text{B}&\text{W}&\text{B}\\\text{W}&\text{B}&\text{W}&\text{W}\\\text{W}&\text{B}&\text{W}&\text{B}\end{matrix} \quad \Rightarrow \quad \begin{matrix}0&0&1&0\\1&1&0&1\\0&1&0&0\\0&1&0&1\end{matrix}$$

很明显的可以看出，若一个矩阵为白色矩阵，则其包含的数之和为 $0$ 。所以我们可以暴力 $O(n^4)$ 枚举每个矩阵判断。

然而这题能用二维前缀和做的根本原因是数据太水

那么接下来就是二维前缀和的部分。

$sum[n][m]$ 表示左上角为 $(1,1)$ 右下角为 $(n,m)$ 的这个子矩阵中所有数的和。即：

$$sum[n][m] = \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m}map[i][j]$$

易得：

$$sum[n][m] = sum [n - 1][m] + sum[n][m - 1] - sum[n - 1][m - 1] + map[n][m]$$

这个画张图看一看就知道了。

如果想得到左上角为 $(i,j)$ 右下角为 $(k,l)$ 的这个子矩阵中所有数的和：

$$ans = sum[k][l] - sum[i - 1][l] - sum[k][j - 1] + sum[i - 1][j - 1]$$

这个也可以画张图推出来。

于是我们就可以水掉一道蓝题了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

const int N = 150;

int n, ans;
int map[N + 5][N + 5];
int sum[N + 5][N + 5];

void pre()
{
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			sum[i][j] = sum [i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + map[i][j];
}

int main()
{
	scanf("%d", &n);
	char c;
	for (int i = 1; i <= n; i ++)
	{
		for (int j = 1; j <= n; j ++)
		{
			std::cin >> c; //输入有坑，可能有空格
			map[i][j] = (c == 'B');
		}
	}
	pre();
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)
			for (int k = i; k <= n; k ++)
				for (int l = j; l <= n; l ++)
					if (sum[k][l] - sum[i - 1][l] - sum[k][j - 1] + sum[i - 1][j - 1] == 0)
						ans ++;
	printf("%d", ans);
	return 0;
}