[Daimayuan] 巨大的牛棚（C++，矩阵前缀和）

题目描述

农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 n * n的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。 考虑下面的方格，它表示农夫约翰的农场，.表示没有树的方格，#表示有树的方格

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

那么最大的牛棚是5*5的。

输入描述

第一行输入一个正整数 $n(1\le n\le 1000)$代表农场的大小，一个正整数$T(1\le T\le n\ast n)$， 接下来 $T$ 行，每行$2$个整数，代表有树的格子的横纵坐标，保证任意两个树格子不相同

输出描述

输出一个正整数代表牛棚的最大边长

样例输入

8 3
2 2
2 6
6 3

样例输出

5

解题思路

可以看出问题具有单调性：牛棚越大，修建的可能性越小；反之，可能性越大

而我们需要找出可能修建的最大的牛棚，所以采用二分法

int bin_search() {int l = 0, r = w + 1, m;while (l + 1 != r) {m = (l + r) / 2;if (judge(m)) l = m;else r = m;}return l;
}

然后就是如何实现judge函数的问题了

显然，判断牛棚大小是否可行，需要遍历所有可能的位置，采用二重循环实现

bool judge(int m) {for (int i = 1; i <= w - m + 1; i++) {for (int j = 1; j <= w - m + 1; j++) {if (找到可行位置) return true;}}return false;
}

那么最后一个问题：找到可行位置的条件是什么？

如果一棵一棵树判断，肯定TLE的飞起，所以需要想一想其他方法

这时候就要提到矩阵前缀和的概念了，这一方法应用于矩阵中，用于降低判断的时间复杂度

规定pre[x][y]=∑1≤i≤x∑1≤j≤ymap[i][j]pre[x][y]=\\sum_{1 \\le i \\le x}{\\sum_{1 \\le j \\le y}{map[i][j]}}pre[x][y]=∑1≤i≤x​∑1≤j≤y​map[i][j]

其中map为二维bool数组，有树为true，无树为false

接下来介绍另外一个原理：包含排斥原理

首先看一下下面这张图

我们要计算$4$号区域的sum4sum_4sum4​则有sum4=sum1,2,3,4−sum1,2−sum1,3+sum1sum_{4}=sum_{1,2,3,4}-sum_{1,2}-sum_{1,3}+sum_{1}sum4​=sum1,2,3,4​−sum1,2​−sum1,3​+sum1​

这就是包含排斥原理的简单理解，也足够我们解决这道题了

应用以上两个概念，我们可以计算出指定区域内的矩阵和，如果和为$0$则可行；反之，继续尝试下一个区域

最后，AC代码如下

#include <iostream>
using namespace std;
const int max_n = 1e3;int w, n;
bool map[max_n + 1][max_n + 1];
int pre[max_n + 1][max_n + 1];bool judge(int m) {for (int i = 1; i <= w - m + 1; i++) {for (int j = 1; j <= w - m + 1; j++) {int x = i + m - 1, y = j + m - 1;if (!(pre[x][y] - pre[x][j - 1] - pre[i - 1][y] + pre[i - 1][j - 1]))return true;}}return false;
}int bin_search() {int l = 0, r = w + 1, m;while (l + 1 != r) {m = (l + r) / 2;if (judge(m)) l = m;else r = m;}return l;
}int main() {cin >> w >> n;int x, y;for (int i = 1; i <= n; i++) {cin >> x >> y;map[x][y] = true;}for (int i = 1; i <= w; i++) {for (int j = 1; j <= w; j++) {pre[i][j] = map[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];}}cout << bin_search() << endl;return 0;
}