题目5：最大连通块

问题描述

思路

此题可以用DFS遍历每个位置上的数是1的结点，用计数变量cnt来表示每个子节点含有连通分块的数量,然后进行累加，因此每个位置只能遍历一次，在递归回溯的时候，不用恢复现场。

代码部分

• 方法一：DFS

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int a[40][70],b[40][70];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int res=-0x3f3f3f3f;
int dfs(int x,int y)
{
	int cnt=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=1&&nx<=30&&ny>=1&&ny<=60&&!b[nx][ny]&&a[nx][ny]==1)
		{
			b[nx][ny]=1;
			cnt+=dfs(nx,ny);
//			b[nx][ny]=0;// 没有回溯
		}
	}
	return cnt;
}
int main ()
{
	for(int i=1;i<=30;i++){
		for(int j=1;j<=60;j++){
			cin>>a[i][j];
		} 
	}
	for(int i=1;i<=30;i++){
		for(int j=1;j<=60;j++)
		{
			b[i][j]=1;
			res=max(res,dfs(i,j));
//			b[i][j]=0; //没有回溯
		}
	}
	cout<<res<<endl;
	return 0;
}

• 方法二：记忆化搜索

#include <bits/stdc++.h>
using namespace std;
int a[35][65],b[35][65],c[35][65];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int Maxn=-0x3f3f3f3f;
int dfs(int x,int y)
{
	int cnt=1;
	if(c[x][y]!=-1) return cnt+c[x][y];
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=1&&nx<=5&&ny>=1&&ny<=5&&a[nx][ny]==1&&!b[nx][ny])
		{
			b[nx][ny]=1;
			cnt+=dfs(nx,ny);
		}
	}
	c[x][y]=cnt;
	return c[x][y];
}
int main ()
{
	memset(c,-1,sizeof c);
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		{
			if(a[i][j]==1)
			{
				b[i][j]=1;
				Maxn=max(Maxn,dfs(i,j));
			}
		}
	}
	cout<<Maxn<<endl;
	return 0;
}

• 方法三：BFS

#include <bits/stdc++.h>
using namespace std;
const int N=1e2+10;
typedef pair<int,int> PII;
queue<PII> q;
int a[N][N],b[N][N];//b[N][N]数组不仅代表是否遍历，且代表到此点要多少步 
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int n,m;
int bfs(int x,int y)
{
	int cnt=1;// 在主函数中已经判断(x,y)这个点是1，所以cnt的初始值为1
	b[x][y]=1;
	q.push({x,y});
	while(!q.empty())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=t.first+dx[i],ny=t.second+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]==1&&!b[nx][ny])
			{
				b[nx][ny]=1;
				q.push({nx,ny});
				cnt++;
			}
		}
	}
	return cnt;
}
int main ()
{
	cin>>n>>m; 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	int res=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!b[i][j]&&a[i][j]==1) // 每个点只能遍历一次
			{
				res=max(res,bfs(i,j));	
			}
	cout<<res<<endl;
	return 0;
}