P1191 矩形

------------恢复内容开始------------

题意

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

分割线

Ⅰ.暴力出奇迹!!!

①枚举矩形左上角的点(两重循环)

②枚举矩形的长和宽(两重循环)

③一个点一个点得验证矩形是否合法(两重循环)

但是非非非非常明显的,步骤三可以优化掉。

\(我们想要的不过是矩形内都是白色，二位前缀和可以很方便的做到。\)
\(假如白色是代表1，黑色代表2，那么矩形的值应该是它面积的大小\)

\(所以4重循环还是很快的!!\)

#include <bits/stdc++.h>

using namespace std;

int n,sumn[159][159];

char a[159][159];

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++)

	for(int j=1;j<=n;j++)

	{

		cin>>a[i][j];

		int k=0;

		if(a[i][j]=='W')	k=1;

		sumn[i][j]=sumn[i-1][j]+sumn[i][j-1]+k-sumn[i-1][j-1];

	}

	int ans=0;

	for(int i=1;i<=n;i++)//枚举长

	for(int j=1;j<=n;j++)//枚举高

	for(int q=1;q+i-1<=n;q++)

	for(int w=1;w+j-1<=n;w++)

	{

		int temp;

		int x=i+q-1,y=j+w-1;

		temp=sumn[x][y]-sumn[q-1][y]-sumn[x][w-1]+sumn[q-1][w-1];

		if(temp==i*j)	ans++;

	}

	cout<<ans;

}

Ⅱ.\(n^3\)做法

虽然看懂了，但感觉并不是很好理解

想了解请点我(●'◡'●)

------------恢复内容结束------------

巴特西

P1191 矩形

分割线

Ⅰ.暴力出奇迹!!!

Ⅱ.\(n^3\)做法

最新文章

热门文章