洛谷AT319 3Match

洛谷AT319 3Match 题目传送门 题意翻译 题目描述

有 H 行 W 列的矩阵，每一个矩阵都有一个数字填充。我们需要找出连续的横着 3 个及以上或竖着 3 个及以上的，由同一数字构成的长方形，如图：

但是，这有可能会连通。那么，这些连通的只会变成一个。如图： 

需要求出长方形的个数（连通的只算一个）

输入格式

第一行两个正整数 N 和 M。

第二行到第 N + 1 行，每一行 M 个由 0 到 9 的数，没有空格。

输出格式

一个正整数，表示长方形的个数（连通的只算一个）

输入输出样例

样例 1

输入：

3 5
12302
22202
23102

输出：

3

如下图，有 3 个长方形。

样例 2

输入：

3 6
111234
231114
332332

输出：

1

如下图，由于连通，所以只输出 1 个。

数据范围

3≤H,W≤100

思路：用bfs或dfs都可以！！！

bfs:

#include
using namespace std;
int n,m,ans,q[100010][2],zx[4]= {1,-1,0,0},zy[4]= {0,0,1,-1};
char a[1010][1010];
bool f[1010][1010];
void bfs(int x,int y,char ch) {
	ans++;
	f[x][y]=false;
	int head=1,tail;
	q[++tail][0]=x,q[tail][1]=y;
	while(head<=tail) {
		for(int i=0; i<4; i++) {
			int dx=q[head][0]+zx[i],dy=q[head][1]+zy[i];
			if(f[dx][dy]&&a[dx][dy]==ch) {//找到了
				f[dx][dy]=false;
				q[++tail][0]=dx,q[tail][1]=dy;
			}
		}
		head++;
	}
}
int main() {
	cin>>n>>m;
	memset(f,false,sizeof(f));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>a[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(a[i][j]==a[i][j+1]&&a[i][j]==a[i][j+2]) f[i][j]=f[i][j+1]=f[i][j+2]=true;//可以成为目标
			if(a[i][j]==a[i+1][j]&&a[i][j]==a[i+2][j]) f[i][j]=f[i+1][j]=f[i+2][j]=true;//同上
		}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(f[i][j]
				bfs(i,j,a[i][j]);//因为可以连通
	cout<

dfs：

#include
using namespace std;
int n,m,ans;
char a[1010][1010];
bool f[1010][1010];
void dfs(int x,int y,char ch) {
	if (x==0||y==0||x>n||y>m||!f[x][y]||a[x][y]!=ch) return ;//不能做为目标
	f[x][y]=false;
	dfs(x,y-1,ch);//寻找下一个目标
	dfs(x,y+1,ch);
	dfs(x-1,y,ch);
	dfs(x+1,y,ch);
}
int main() {
	cin>>n>>m;
	memset(f,false,sizeof(f));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>a[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(a[i][j]==a[i][j+1]&&a[i][j]==a[i][j+2]) f[i][j]=f[i][j+1]=f[i][j+2]=true;
			if(a[i][j]==a[i+1][j]&&a[i][j]==a[i+2][j]) f[i][j]=f[i+1][j]=f[i+2][j]=true;
		}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(f[i][j])
				ans++,dfs(i,j,a[i][j]);//因为dfs是循环的,所以ans得在if里加
	cout<