BFS基本概念

广度优先算法（Breadth-First-Search），简称BFS，是一种图形搜索演算法，最糟糕的情况算法时间复杂度为O(V+E)。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。

经典例题

1. 填涂颜色

题目描述

由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22。例如：6×66×6的方阵(n=6)(n=6)，涂色前和涂色后的方阵如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
-----------
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1≤n≤30)n(1≤n≤30)

接下来nn行，由00和11组成的n×nn×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个00。

输出格式

已经填好数字22的完整方阵。

输入输出样例

输入 #1

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出 #1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

说明/提示

1≤n≤301≤n≤30

答案解析

#include<iostream>
using namespace std;
int num[40][40];
int main()
{
    int c,i,j,k;
    cin>>c;
    for(i=1;i<=c;i++)
		for(j=1;j<=c;j++)
    {
        cin>>num[i][j];
        if(num[i][j]==0)
			num[i][j]=2;
        //先认为所有的0都应该被修改,并且真的把它修改成了2;
    }
    for(i=1;i<=c;i++)
    {
        //边角上的'2'其实本来不应该被修改的,那我们把他们改回去,改成0
        if(num[1][i]==2)
			num[1][i]=0;
        if(num[i][1]==2)	
			num[i][1]=0;
        if(num[c][i]==2)
			num[c][i]=0;
        if(num[i][c]==2)
			num[i][c]=0;
    }
    //然后来寻找与这些零相邻的'2',它们其实也是被改错了的
    for(k=1;k<=100;k++)//广度优先搜索 阈值=100 (事实上不需要那么多)
    	for(i=1;i<=c;i++)
    		for(j=1;j<=c;j++)
    		    if(num[i][j]!=1)
    			    if(!num[i][j-1]||!num[i-1][j]||!num[i+1][j]||!num[i][j+1])
    				    num[i][j]=0; 
    for(i=1;i<=c;i++)
    {
        for(j=1;j<=c;j++)
        cout<<num[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

当然，本题仍可以用DFS来做：

#include <cstdio>
using namespace std;
int n;
int a[32][32];
void dfs(int x, int y)
{
    if(x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1)
    {
        if(a[x][y] == 1 || a[x][y] == 3) 
        	return ;
        else
        {
        	a[x][y] = 3;
            dfs(x + 1, y); 
            dfs(x - 1, y);
            dfs(x, y + 1); 
            dfs(x, y - 1);
        }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
    	for(int j = 1; j <= n; ++ j)
    		scanf("%d", &a[i][j]);
    dfs(0, 0);
    for(int i = 1; i <= n; ++ i)
    	for(int j = 1; j <= n; ++ j)
    		if(a[i][j] == 3) 
    			a[i][j] = 0;
    		else 
    			if(a[i][j] == 0) 
    				a[i][j] = 2;
    for(int i = 1; i <= n; ++ i)
    {
    	for(int j = 1; j <= n; ++ j) 
    		printf("%d ", a[i][j]);
    	printf("\n")
    }
    return 0;
}

注意：dfs在先搜索的时候应该搜索到矩阵的外面一圈(0，n+1)(0， n + 1) 否则的话就会出现错误！(边缘处被涂色)

01迷宫

题目描述

有一个仅由数字00与11组成的n×nn×n格迷宫。若你位于一格00上，那么你可以移动到相邻44格中的某一格11上，同样若你位于一格11上，那么你可以移动到相邻44格中的某一格00上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式

第11行为两个正整数n,mn,m。

下面nn行，每行*nn*个字符，字符只可能是00或者11，字符之间没有空格。

接下来mm行，每行22个用空格分隔的正整数i,ji,j，对应了迷宫中第ii行第jj列的一个格子，询问从这一格开始能移动到多少格。

输出格式

mm行，对于每个询问输出相应答案。

输入输出样例

输入 #1

2 2
01
10
1 1
2 2

输出 #1

4
4

说明/提示

对于20%的数据，n≤10n≤10；

对于40%的数据，n≤50n≤50；

对于50%的数据，m≤5m≤5；

对于60%的数据，n∗≤100,∗m≤100n*≤100,*m≤100；

对于100%的数据，n∗≤1000,∗m≤100000n*≤1000,*m≤100000。

答案解析

BFS，70分代码：

#include<iostream>
#include<cstring>
using namespace std;
struct mg
{
    int x,y;
};
bool map[1001][1001];
bool flag[1001][1001];
mg q[1000001];
int m,n;
void bfs(int x,int y);
int main()
{
	cin>>n>>m;
	char ch;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>ch;
			if(ch=='1')
				map[i][j]=true;
		}
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		bfs(x,y);
	}
	return 0;
}
void bfs(int x,int y)
{
	int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int ans,f,r,newx,newy;
    ans=f=r=1;
    q[f].x=x;
    q[f].y=y;
    memset(flag,false,sizeof(flag));
    flag[x][y]=true;
    while(f<=r)
    {
    	for(int i=0;i<4;i++)
    	{
    		newx=q[f].x+dx[i];
    		newy=q[f].y+dy[i];
    		if(newx>0 && newx<=n && newy>0 && newy<=n && !flag[newx][newy])
    			if((map[q[f].x][q[f].y]==0 && map[newx][newy]==1) || (map[q[f].x][q[f].y]==1 && map[newx][newy]==0))
    			{
    				r++;
    				ans++;
    				flag[newx][newy]=true;
    				q[r].x=newx;
    				q[r].y=newy;
				}
		}
		f++;
	}
	cout<<ans<<endl;
 }

有三个点TEL，所以对代码进行一定时间优化，学名叫记忆化搜索，以时间换空间，优化如下：

#include<iostream>
#include<cstring>
using namespace std;
struct mg
{
    int x,y;
};
bool map[1001][1001];
bool flag[1001][1001];
int a[1001][1001];
mg q[5000001];
int m,n;
void bfs(int x,int y);
int main()
{
	cin>>n>>m;
	char ch;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>ch;
			if(ch=='1')
				map[i][j]=true;
		}
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		if(a[x][y]==0)
			bfs(x,y);
		else
			cout<<a[x][y]<<endl;
	}
	return 0;
}
void bfs(int x,int y)
{
	int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int ans,f,r,newx,newy;
    ans=f=r=1;
    q[f].x=x;
    q[f].y=y;
    memset(flag,false,sizeof(flag));
    flag[x][y]=true;
    while(f<=r)
    {
    	for(int i=0;i<4;i++)
    	{
    		newx=q[f].x+dx[i];
    		newy=q[f].y+dy[i];
    		if(newx>0 && newx<=n && newy>0 && newy<=n && !flag[newx][newy])
    			if((map[q[f].x][q[f].y]==0 && map[newx][newy]==1) || (map[q[f].x][q[f].y]==1 && map[newx][newy]==0))
    			{
    				r++;
    				ans++;
    				flag[newx][newy]=true;
    				q[r].x=newx;
    				q[r].y=newy;
				}
		}
		f++;
	}
	for(int i=1;i<n;i++)
		for(int j=1;j<n;j++)
			if(flag[i][j])
				a[i][j]=ans;
	cout<<ans<<endl;
 }

当然，本题也可以用DFS来做，读者可以先自行写一写，不要看下面的答案：

#include<cstdio>
#include<cstring>
int n,m,x,y;
int ans[100002],f[1002][1002];
char s[1002][1002];
void dfs(int r,int c,int z,int lll)
{
    if (r<0 || r>=n || c<0 || c>=n || f[r][c]!=-1 || s[r][c]-'0'!=z)
        return;
    f[r][c]=lll;
    ans[lll]++;
    dfs(r-1,c,!z,lll);
    dfs(r+1,c,!z,lll);
    dfs(r,c-1,!z,lll);
    dfs(r,c+1,!z,lll);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
    	scanf("%s",s[i]);
    memset(f,-1,sizeof(f));
    for (int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        x--;
        y--;
        if (f[x][y]==-1)
            dfs(x,y,s[x][y]-'0',i);
        else 
            ans[i]=ans[f[x][y]];
    }
    for (int i=0;i<m;i++)
    	printf("%d\n",ans[i]);
    return 0;
}

ENDEND