（新版）SJTU-OJ-1008. LSZ的雪地脚印

本文主要是介绍（新版）SJTU-OJ-1008. LSZ的雪地脚印，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

2006年冬的某一天上午下了一场大雪，TSYZ教学楼下的排球场上覆盖了一层雪。

下课了，很多人来到这里，留下了很多脚印。

排球场可以看作是由N×M的方格组成的一个矩形，其中某些方格已经有脚印了，而剩下的则是完好的。

lsz想在上面写下自己的名字，也就是"lsz"三个字母，为了美观，要求这三个字母必须占据一个2:1(横向的，不能是1:2)的完好矩形，

也就是说，在这个2:1的矩形内不得有脚印。

现在给你场地的脚印情况，lsz想知道自己的名字最大可以占据多大面积。

输入格式

第一行为空格分隔的两个正整数，N和M，表示场地的大小。

下面有N行，每行M个字符，每个字符要么是-(减号)，表示该方格完好，要么是X(大写的x)，表示该方格有脚印。

输出格式

一个正整数，表示"lsz"最大可以占据多大面积。

样例输入

4 6
X--XXX
----X-
------
-X--X-

样例输出

数据范围

40%的数据满足 $N,M<123$

100%的数据满足 $0<N,M<1234$

题目吐槽

首先，这年代有点久远了，不知道是老题目还是就蹭着那句歌词玩玩

然后，TSYZ教学楼是什么啊，和交大有关系吗，我也不是很知道，希望有人能解答

lsz应该是个人名吧，不认识也不需要介意这个

突然想起来好像有听说（或者是见到emmm不记得了应该是听说吧）利用什么在雪地上写字表白的emmm就很神奇，不过emmm估计就写到这里吧，不能再BB了

这家伙占地盘可还行，还要我帮忙算能占多少地盘，hhh

上面是关于题面的吐槽，接着，下面是！

这题太难了呜呜呜，刚刚去百度了一波，没有找到一样的题目，看来是新题

这个有点厉害真的真的真的，一般的最容易想到的基本上肯定过不了，能过的都是nb

在一位公开了代码的同学帮助下还是顺利完成了好耶！

感谢一波（虽然可能也不认识）

题目解答

老套路，毕竟是初学c++，最先想到的基本上都不对过不了，哪怕是对的往往也是卡在时间的节点上，不过嘛既然是学习那还是慢慢来，先看最容易想到的暴力枚举方法吧

读数据就不用说了，没有什么特别的，定义一个字符串的矩阵，然后一个一个读取就可以了。然后判断什么的用字符串的比较就可以。

这里强调一下比较的方法是

char ch;cin >> ch;
if (ch == 'X')    //正确
if (ch == "X")    //错误

看来程序员都有一个共性就是几天前写的代码都忘记什么了2333

刚刚看了一下记录，下面这段代码可以拿60分hhhh

#include <iostream>
using namespace std;int n,m;
char array[1240][1240];                          //养成好习惯，空间一次性开满
bool IfAvailable(int line, int colony, int scale);//这个函数判断已知左上角和规模是否可行
bool PositionFocus(int scale);                   //这个函数用来定位每一个左上角//其实后面两个函数是紧密关联的//第二个函数可以调用第一个函数
int main()
{cin >> n >> m;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> array[i][j];}                                        //读数据呗}                                            int ans;//这里还是要多说几句，因为m，n大小也不知道，所以最大的规模k能多少也不知道
//那么我们知道，情况一 m>= 2*k 且 n>=k
//             情况二 m>= k   且 n>= 2*k
//所以，最大的k = max(min(m, n / 2), min(n, m / 2))
//其实这里有两个思路一个是k从1开始往上爬
//另外一个是k从最大的开始递减hhh，后来发现递减的分数拿的比递增的分数高 nice虽然都没有过for (int k = max(min(m, n / 2), min(n, m / 2)); k >= 1; k--){if (PositionFocus(k) == true){ans = k;break;}}cout << ans * ans * 2;system("pause");return 0;
}//小结一下，主函数还是蛮简洁的个人觉得

这个代码看着我都头大，还是费力爬上去写完了注释。

似乎分开来看更合适，

考虑到不同规模的情况下，左上角的横纵坐标的范围不同，所以用这个函数根据scale规模来确定位置

.	.	.	.	.	.
.
.
.

上图中：粉色的为定位点，黄色的是预备检测的区域。那么可以根据定位点以及规模确定整个区域啦，上图就是2*4规模的写字区域

我们定义左上角的坐标为（1,1）那么当规模为2（即为 $2\times 4$ ）时候的定位点的可行区域是绿色部分

.	.	.	.	.	.
.
.
.

所以说白了就是emmm下面这个函数用来扫描这个绿色的区域，让定位点依次经过上面绿色部分的每一个地方

只要找到规模为k的任意一个可行的解决方法，函数结束，返回true 可以找到！

//下面这个PositionFocus用于定位，目的就是把所有可以的情况检测一遍
bool PositionFocus(int scale)
{for (int i = 0; i < n + 1 - scale; i++){for (int j = 0; j < m - scale * 2 + 1; j++){if (array[i][j]=='X')continue;else if (IfAvailable(i, j, scale)==true)return true;//找到一个就结束}}return false;
}

每次确定一个定位点后需要检测这个区域是否可以放下所有的，只要有一个脚印，函数结束返回不可以

bool IfAvailable(int line,int colony,int scale)
{bool tempresult = true;for (int a = line; a <= line + scale - 1; a++){for (int b = colony; b <= colony + 2 * scale - 1; b++){if (array[a][b]=='X'){return false;}}}return tempresult;
}

评测结果60分。显然不是我们需要的

所以呢我们要改进方法啦，我们要用数学的方法来解决这种问题，改进时候参考了别人的代码中的思想，但是还是基于自己的代码修改的，修改的仅仅是IfAvailable这个函数，以及输入的部分。

可以看到，之前的IfAvailable有两个嵌套循环，时间复杂度较大，所以改进如下

bool IfAvailable(int x,int y,int scale)
{if (array[x - 1][y - 1] + array[x + scale - 1][y + 2 * scale - 1] - array[x - 1][y + 2 * scale - 1] - array[x + scale - 1][y - 1] == 0)return true;elsereturn false;
}

看上去这个代码很长，而且还出现了一个二维数组array，但是简洁明了，用一个数学表达式解决了判断的问题。

原理是什么呢？

我们不妨叫做堆叠法吧（我也不知道是不是这个名字）

先从一维数组开始

我们高中就学习过数列，知道根据数列的前 $n$ 项和可以求出每一项 $a_n$ ，公式如下：

$\begin{equation} a_n=\left\{ \begin{aligned} S_1 \quad \quad \quad n=1\\ S_n-S_{n-1} \quad n\geq 2\\ \end{aligned} \right . \end{equation}$

同理对于数组 $a_n$ 也可以用类似的方法表示，构造一个前缀数组

原数组：

1	2	3	4	5	6	……	$n-1$	$n$
$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$		$a_{n-1}$	$a_n$

新数组：

1	2	3	4	5	6	……	$n-1$	$n$
$a_1$	$\sum_{i=1}^{2}a_i$	$\sum_{i=1}^{3}a_i$	$\sum_{i=1}^{4}a_i$	$\sum_{i=1}^{5}a_i$	$\sum_{i=1}^{6}a_i$		$\sum_{i=1}^{n-1}a_i$	$\sum_{i=1}^{n}a_i$

类似的，二维数组我们也可以构造前缀和：

原数组：

$a_{11}$	$a_{12}$	$a_{13}$	$a_{14}$	.....	$a_{1j}$
$a_{21}$	$a_{22}$	$a_{23}$
$a_{31}$	$a_{32}$
$a_{41}$
.....				$a_{i-1,j-1}$	$a_{i-1,j}$
$a_{i1}$				$a_{i,j-1}$	$a_{i,j}$

新的数组：

$\sum_{j=1}^{1}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{2}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{3}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{4}\sum_{i=1}^{1}a_{ij}$	......	$\sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{2}a_{ij}$	$\sum_{j=1}^{2}\sum_{i=1}^{2}a_{ij}$	$\sum_{j=1}^{3}\sum_{i=1}^{2}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{3}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{4}a_{ij}$
.....				$\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}$	$\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{n}a_{ij}$				$\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}$	$\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}$

好家伙这个看上去确实很复杂，需要怎样才能构建这个新的数组呢

首先，原数组的读取就不用多说了，两层for循环就可以搞定，读取数据。

但是新数组的构建应该如何呢，暴力方法是对于每个坐标 $(m,n)$ 计算 $\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}$ ，确实如此，但是计算方法如果在使用嵌套循环太麻烦了。

所以，有下面的公式：

$\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}+\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}-\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}$

把公式翻译成代码就是：

array[m][n] = array[m][n - 1] + array[m - 1][n] - array[m - 1][n - 1];

如果你觉得不好理解那可以画图验证一下下，减去的那一部分是重复的(黄色部分hhh)

我们还是看这一表格吧，会好理解一些

$a_{11}$	$a_{12}$	$a_{13}$	$a_{14}$	.....	$a_{1j}$
$a_{21}$	$a_{22}$	$a_{23}$
$a_{31}$	$a_{32}$
$a_{41}$
.....				$a_{i-1,j-1}$	$a_{i-1,j}$
$a_{i1}$				$a_{i,j-1}$	$a_{i,j}$

在比照一下下面这个东西

$\sum_{j=1}^{1}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{2}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{3}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{4}\sum_{i=1}^{1}a_{ij}$	......	$\sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{2}a_{ij}$	$\sum_{j=1}^{2}\sum_{i=1}^{2}a_{ij}$	$\sum_{j=1}^{3}\sum_{i=1}^{2}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{3}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{4}a_{ij}$
.....				$\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}$	$\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{n}a_{ij}$				$\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}$	$\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}$

所以其实在读取数据的时候就可以完成数据的处理了，用那个公式就可以

所以，简化算法流程的关键在于，用数学运算来检测X位置

用一个新的数组（或者就在原数组的基础上面）

$c_{mn}=\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}$

表示

那么下面是代码部分啦！

下面是数据读取的部分代码，X是不可以防止的地方，别的是可以的，所以只要为X就把对应的那个 $a_{mn}$ 加一，(我这个编译器数组默认是全部为0)，这也为后面的操作提供了便利

    cin >> n >> m;    //题目已定义的数据输入for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){char ch;cin >> ch;array[i][j] = array[i][j - 1] + array[i - 1][j] - array[i - 1][j - 1];//注意，这里先完成数据的预处理，再检查是不是Xif (ch == 'X'){ array[i][j]++;      //是X就再加一吧，不是就不用管，顺序关注一下即可}}}

接下来，我改进了IfAvailable这个函数（这个函数是在已知预检测区域左上角的坐标以及规模的前提下，检测整个区域是否有X）

那好说啦，检测这个区域有没有X，只需要用这个公式就可以。这个代码有点长

if (array[x-1][y-1]+array[x+scale-1][y+2*scale-1]-array[x-1][y+2*scale-1]-array[x+scale-1][y-1]==0)
// x，y表示左上定位点坐标
// scale表示检测区域的规模，为短边的大小

换一种解释（可以理解的）：

$a_{11}$	$a_{12}$	$a_{13}$		.....	$a_{1j}$
$a_{21}$	$a_{22}$
$a_{31}$
		$a_{x-1,y-1}$
.....			$a_{x,y}$	$a_{i-1,j-1}$	$a_{i-1,j}$
$a_{i1}$				$a_{i,j-1}$	$a_{i,j}$

$\sum_{j=1}^{1}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{2}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{3}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{4}\sum_{i=1}^{1}a_{ij}$	......	$\sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}$	$\sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{2}a_{ij}$	$\sum_{j=1}^{2}\sum_{i=1}^{2}a_{ij}$	$\sum_{j=1}^{3}\sum_{i=1}^{2}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{3}a_{ij}$	.......	.......	.......	......	.......	.......
......		$\sum_{j=1}^{x-1}\sum_{i=1}^{y-1}a_{ij}$
.....			$\sum_{j=1}^{x}\sum_{i=1}^{y}a_{ij}$	.......	$\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}$	$\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}$
$\sum_{j=1}^{1}\sum_{i=1}^{n}a_{ij}$			......	$\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}$	$\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}$	$\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}$

按照上图的解释，检测区域如图，监测区域的定位点为 $(m,n)$ , $a_{i,j}$ 表示该区域X的个数，有为1，没有为0，

$\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}$ 表示从 $(m,n)$ 到 $(1,1)$ 这个矩形的X的个数

为了保证绿色区域没有任何X，则有下面的等式成立：

$\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}+\sum_{j=1}^{x-1}\sum_{i=1}^{y-1}a_{ij}= \sum_{j=1}^{m}\sum_{i=1}^{y-1}a_{ij}+\sum_{j=1}^{x-1}\sum_{i=1}^{n}a_{ij}$

公式翻译过来就是：整个 $(m,n)$ 左上的区域+蓝色区域 =（粉色区域+蓝色区域）+（蓝色区域+白色区域）

左右去掉一样的，就是绿色区域=0，就是说没有X。好机智的算法！

下面是IfAviarlable函数的改进版，

bool IfAvailable(int x,int y,int scale)
{if (array[x - 1][y - 1] + array[x + scale - 1][y + 2 * scale - 1] - array[x - 1][y + 2 * scale - 1] - array[x + scale - 1][y - 1] == 0)return true;elsereturn false;
}

最后上以下完整的AC代码，毕竟前面已经解释很清楚啦，就没有单独加注释hhh偷个懒

#include <iostream>
using namespace std;int n,m;
int array[1240][1240];bool PositionFocus(int scale);
bool IfAvailable(int x, int y, int scale);int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){char ch;cin >> ch;array[i][j] = array[i][j - 1] + array[i - 1][j] - array[i - 1][j - 1];if (ch == 'X'){ array[i][j]++;}}}int ans;for (int k = 1; k <= n; k++){if (PositionFocus(k) == false){ans = k-1;break;}}cout << ans * ans * 2;system("pause");return 0;
}bool PositionFocus(int scale)
{for (int i = 1; i <= n + 1 - scale; i++){for (int j = 1; j <= m - scale * 2 + 1; j++){if (IfAvailable(i, j, scale) == true)return true;//找到一个就结束}}return false;
}bool IfAvailable(int x,int y,int scale)
{if (array[x - 1][y - 1] + array[x + scale - 1][y + 2 * scale - 1] - array[x - 1][y + 2 * scale - 1] - array[x + scale - 1][y - 1] == 0)return true;elsereturn false;
}

这篇关于（新版）SJTU-OJ-1008. LSZ的雪地脚印的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！