连通块

连通块连通块
连通块
连通块

#include <iostream>
#include <deque>
#include <string>
#include<cstdio>
#define MAX 300
using namespace std;
struct Point {
	int x;
	int y;
	Point(int _x, int _y) :x(_x), y(_y) {}
};
void BFS(int **a, int n, int m, int x, int y,bool **visit)
{
	deque<Point> Q;
	Q.push_back(Point(x, y));
	while (!Q.empty())
	{
		Point temp = Q.front();
		Q.pop_front();
		int temp_x = temp.x;
		int temp_y = temp.y;
		visit[temp_x][temp_y] = true; 
		if (temp_x - 1 >= 0 && temp_x - 1 < n&&temp_y >= 0 && temp_y < m)
		{
			if (!visit[temp_x - 1][temp_y] && a[temp_x - 1][temp_y] != 0)
				Q.push_back(Point(temp_x - 1, temp_y));
		}
 
		if (temp_x + 1 >= 0 && temp_x + 1 < n&&temp_y >= 0 && temp_y < m)
		{
			if (!visit[temp_x + 1][temp_y] && a[temp_x + 1][temp_y] != 0)
				Q.push_back(Point(temp_x + 1, temp_y));
		}
 
		if (temp_x >= 0 && temp_x < n&&temp_y - 1 >= 0 && temp_y - 1 < m)
		{
			if (!visit[temp_x][temp_y - 1] && a[temp_x][temp_y - 1] != 0)
				Q.push_back(Point(temp_x, temp_y - 1));
		}
 
		if (temp_x >= 0 && temp_x < n&&temp_y + 1 >= 0 && temp_y + 1 < m)
		{
			if (!visit[temp_x][temp_y + 1] && a[temp_x][temp_y + 1] != 0)
				Q.push_back(Point(temp_x, temp_y + 1));
		}
	}
}
int main()
{
	int n, m;
	scanf("%d %d",&n,&m);
		int **a=new int*[n];
	for(int i=0;i<n;i++)
	{
		a[i]=new int[m]();
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			scanf("%1d",&a[i][j]);
		}
	}
/*	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		for (int j = 0; j < m; j++)
			a[i][j] = temp[j] - '0';
	}*/
 int xx;
 cin>>xx;
 while(xx--)
 {
 			bool **visit=new bool*[n];
	for(int i=0;i<n;i++)
	{
		visit[i]=new bool[m]();
	}
 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visit[i][j] = false;
 	int x1,y1,x2,y2;
 		cin>>x1>>y1>>x2>>y2;
 		for(int i=x1-1;i<=x2-1;i++)
 		{
 			for(int j=y1-1;j<=y2-1;j++)
 			{
 				a[i][j]=1;
 			}
 		}
	int cnt = 0;
	for(int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (!visit[i][j] && a[i][j] != 0)
			{
				++cnt;
				BFS(a, n, m, i, j, visit);
			}
		}
	
	cout << cnt << endl;
 
}
	return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn 1050 //这里设置范围大小
int map[maxn][maxn]; //用来储存图
int visited[maxn][maxn]; //用来标记
int move[8]= {0,1,
              1,0,
              0,-1,
              -1,0
             };  //move数组是求四连通所需要的
int m,n;
void dfs(int r,int c)
{
	if(r<0||r>=m||c<0||c>=n)
		return;
	if(visited[r][c]==1||map[r][c]==0)
		return;
	visited[r][c]=1;
  //这里是求四连通
	for(int i=0; i<=8; i=i+2)
	{
		dfs(r+move[i],c+move[i+1]);
	}
 
}
 
int main()
{


		scanf("%d %d",&m,&n);
		int count=0;
		memset(map,0,sizeof(map));
		for(int i=0; i<m; i++)
		{
			for(int j=0; j<n; j++)
			{
				scanf("%1d",&map[i][j]);
			}
		}
		int x;
		scanf("%d",&x);
		while(x--)
		{
				memset(visited,0,sizeof(visited));
			count=0;
			int x1,y1,x2,y2;
 		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
 		for(int i=x1-1;i<=x2-1;i++)
 		{
 			for(int j=y1-1;j<=y2-1;j++)
 			{
 				map[i][j]=1;
 			}
 		}
		for(int i=0; i<m; i++)
		{
			for(int j=0; j<n; j++)
			{
				if(visited[i][j]==0&&map[i][j]==1)
				{
					dfs(i,j);
					++count;
				}
			}
		}
		printf("%d\n",count);
}
	return 0;
}

上一篇:bfs-迷宫


下一篇:DS图遍历--深度优先搜索