【CF1181C】Flag

题目大意：给定一个 N*M 的矩阵，定义一个矩形区域为一个“国旗”，满足：矩形区域可以按行划分成三个高度相同的部分，其中每一个部分中的颜色完全相同，第一部分的颜色与第二部分颜色不同，第二部分的颜色和第三部分的颜色不同。求给定的矩阵中有多少个不同的国旗，位置不同即为不同。

题解：

首先定义一个数组 d[][]，其中 d[i][j] 表示以第 i 行，第 j 列的元素为顶端，在满足下面颜色和当前位置颜色相同的前提下，能够向下延伸的最长距离。

这道题是一个计数问题，现在定义计数的方式为：计数以每个点为顶点的国旗数量，显然可以保证不重不漏。

对于每个点，d[][] 数组即为第一部分的高度，如果该点可以做成一个国旗，那么要求第二部分的颜色不同于该部分，且第二部分的 d[][] 要和第一部分相等，第三部分同理。

在考虑如何计数宽度大于 1 的部分：对于同一行，维护一个变量 K，遍历每一列，若后一列和前一列相同，则 K++，否则，K=1；若当前列不能组成国旗，则 K=0 即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1010;

typedef long long LL;

int n,m,d[maxn][maxn];LL ans;

char s[maxn][maxn];

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);

	for(int i=n;i>=1;i--)

		for(int j=1;j<=m;j++){

			if(s[i][j]==s[i+1][j])d[i][j]=d[i+1][j]+1;

			else d[i][j]=1;

		}

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

		for(int j=1,k=0;j<=m;j++){

			int h=d[i][j];

			if(i+3*h-1<=n&&d[i+h][j]==h&&d[i+2*h][j]>=h&&s[i][j]!=s[i+h][j]&&s[i+h][j]!=s[i+2*h][j]){

				if(k&&s[i][j]==s[i][j-1]&&d[i][j-1]==h&&s[i+h][j]==s[i+h][j-1]&&d[i+h][j-1]==h&&s[i+2*h][j]==s[i+2*h][j-1]&&d[i+2*h][j-1]>=h)

					++k;

				else

					k=1;

			}

			else k=0;

			ans+=k;

		}

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

【CF1181C】Flag

最新文章

热门文章