基础BFS 邻接矩阵Flood fill 算法题目总结

妖狐艹你老母 2022-09-20 12:50 151阅读 0赞

很基础的一类BFS题，个人觉得BFS在求最短、最近、最快等题目时比DFS还是有较大优势的

**Poj 1979 Red and Black**

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=25;
    struct Point
    {
    	int x,y;
    };
    
    int graph[N][N];
    bool visit[N][N];
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    int W,H,u,v;
    
    int OK (int x,int y)
    {
    	return x>=0 && x<W && y>=0 && y<H;
    }
    
    int BFS ()
    {
    	int ans=1;
    	Point top,t;
        queue <Point> Q;
    	top.x=u;
    	top.y=v;
    	Q.push(top);
    	visit[top.x][top.y]=true;
    	while (Q.empty()==false)
    	{
    		top=Q.front();
    		Q.pop();
    		for (int i=0;i<4;i++)
    		{
    			t.x=top.x+dx[i];
    			t.y=top.y+dy[i];
    			if (OK(t.x,t.y) && graph[t.x][t.y] && !visit[t.x][t.y])
    			{
    				visit[t.x][t.y]=true;
    				Q.push(t);
    				ans++;
    			}
    		}
    	}
    	return ans;
    }
    
    
    int main ()
    {
    	while (scanf("%d%d",&W,&H) , (W || H))
    	{
            char str[N];
            memset(visit,false,sizeof(visit));
            memset(graph,0,sizeof(graph));
            for (int i=0;i<H;i++)
            {
                scanf("%s",str);
                for (int j=0;j<W;j++)
                {
                    if (str[j] == '.')
                        graph[j][i]=1;
                    if (str[j] == '@')
                    {
                        graph[j][i]=1;   //u,v存起点坐标
                        u=j;
                        v=i;
                    }
                }
            }
            printf("%d\n",BFS());
        }
    	return 0;
    }

**Poj 2243 Knight Moves**

题意：要求用象棋中马跳动方式到达终点，求马需要跳动的最少次数。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=10;
    
    struct Point
    {
    	int x,y,step;
    };
    
    int X,Y,n,u,v;
    bool visit[N][N];
    int dx[8] = {1,2,2,1,-1,-2,-2,-1};
    int dy[8] = {2,1,-1,-2,-2,-1,1,2};
    
    int OK (int x,int y)
    {
    	return x>=0 && x<=7 && y>=0 && y<=7 && visit[x][y]==false;
    }
    
    int BFS ()
    {
    	Point top,t;
    	queue <Point> Q;
    	top.step=0;
    	top.x=u;
    	top.y=v;
    	Q.push(top);
    	visit[top.x][top.y]=true;
    	while (Q.empty()==false)
    	{
    		top=Q.front();
    		Q.pop();
    		if (top.x==X && top.y==Y)
    			break;
    		for (int i=0;i<8;i++)
    		{
    			t.x=top.x+dx[i];
    			t.y=top.y+dy[i];
    			t.step=top.step+1;
    			if (OK(t.x,t.y) && !visit[t.x][t.y])
    			{
    				visit[t.x][t.y]=true;
    				Q.push(t);
    			}
    		}
    	}
    	return top.step;
    }
    
    int main ()
    {
    	char ch1[4],ch2[4];
    	while (~scanf("%s%s",&ch1,&ch2))
    	{
    		memset(visit,false,sizeof(visit));
    		u=ch1[0]-'a';
    		v=ch1[1]-'1';
    		X=ch2[0]-'a';
    		Y=ch2[1]-'1';
    		printf("To get from %s to %s takes %d knight moves.\n",ch1,ch2,BFS());
    	}
    	return 0;
    }

**Poj 1915 Knight Moves**

题意：输入n代表有个n\*n的棋盘，输入开始位置的坐标和结束位置的坐标，  
问一个骑士朝棋盘的八个方向走马字步，从开始坐标到结束坐标可以经过多少步。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=305;
    
    struct Point
    {
    	int x,y,step;
    };
    
    int X,Y,n,u,v;
    bool visit[N][N];
    int dx[8] = {1,2,2,1,-1,-2,-2,-1};
    int dy[8] = {2,1,-1,-2,-2,-1,1,2};
    queue <Point> Q;
    
    int OK (int x,int y)
    {
    	return x>=0 && x<=n-1 && y>=0 && y<=n-1 && visit[x][y]==false;
    }
    
    int BFS ()
    {
    	Point top,t;
    	int i;
    	top.step=0;
    	top.x=u;
    	top.y=v;
    	Q.push(top);
    	visit[top.x][top.y]=true;
    	while (Q.empty()==false)
    	{
    		top=Q.front();
    		Q.pop();
    		if (top.x==X && top.y==Y)
    			break;
    		for (i=0;i<8;i++)
    		{
    			t.x=top.x+dx[i];
    			t.y=top.y+dy[i];
    			t.step=top.step+1;
    			if (OK(t.x,t.y))
    			{
    				visit[t.x][t.y]=true;
    				Q.push(t);
    			}
    		}
    	}
    	return top.step;
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	while (T--)
    	{
    		memset(visit,false,sizeof(visit));
    		while (Q.empty()==false)
                Q.pop();
    		scanf("%d%d%d%d%d",&n,&X,&Y,&u,&v);
    		printf("%d\n",BFS());
    	}
    	return 0;
    }

LightOJ 1012 Guilty Prince

题意:给两个数,w,h,表示给一个 高h,宽w的矩阵,  
‘\#’表示不能走,‘.’表示能走,‘@’表示起始点,求从起始点出发能访问多少个点。

#include <queue>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    const int N=25;
    char g[N][N];
    bool visit[N][N];
    int w,h;
    
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    
    struct Node
    {
    	int x,y;
    }temp,cur,s;
    
    bool OK (Node a)
    {
    	if (visit[a.x][a.y]==false && g[a.x][a.y]!='#')
    		return true;
    	return false;
    }
    
    int BFS ()
    {
    	int cnt=0;
    	queue<Node> q;
    	q.push(s);
    	while (!q.empty())
    	{
    		cur = q.front();
    		q.pop();
    		for (int i=0;i<4;i++)
    		{
    			temp.x=cur.x+dx[i];
    			temp.y=cur.y+dy[i];
    			if (OK(temp))
    			{
    				visit[temp.x][temp.y]=true;
    				q.push(temp);
    				cnt++;
    			}
    		}
    	}
    	return cnt;
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d%d",&w,&h);
    		memset(g,'#',sizeof(g));
    		memset(visit,false,sizeof(visit));
    		for (int i=1;i<=h;i++)
    		{
    			scanf("%s",&g[i][1]);
    			g[i][w+1]='#';
    			for (int j=1;j<=w;j++)
    				if (g[i][j]=='@')
    				{
    					s.x=i;
    					s.y=j;
    					visit[s.x][s.y]=true;
    				}
    		}
    		printf("Case %d: %d\n",Cas,BFS()+1);
    	}
    	return 0;
    }

**Poj 3626 Mud Puddles**

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=1005;
    
    struct Point
    {
    	int x,y,step;
    };
    
    int a[N][N],X,Y,n;
    bool visit[N][N];
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    
    int OK (int x,int y)
    {
    	return x>=0 && x<=1000 && y>=0 && y<=1000 && visit[x][y]==false;
    }
    
    int BFS ()
    {
    	Point top,t;
    	queue <Point> Q;
    	top.step=0;
    	top.x=top.y=500;
    	Q.push(top);
    	visit[top.x][top.y]=true;
    	while (Q.empty()==false)
    	{
    		top=Q.front();
    		Q.pop();
    		if (top.x==X && top.y==Y)
    			break;
    		for (int i=0;i<4;i++)
    		{
    			t.x=top.x+dx[i];
    			t.y=top.y+dy[i];
    			t.step=top.step+1;
    			if (OK(t.x,t.y))
    			{
    				visit[t.x][t.y]=true;
    				Q.push(t);
    			}
    		}
    	}
    	return top.step;
    }
    
    int main ()
    {
    	while (~scanf("%d%d%d",&X,&Y,&n))
    	{
    		int i,x,y;
    		memset(visit,false,sizeof(visit));
    		for (i=1;i<=n;i++)
    			scanf("%d%d",&x,&y),visit[x+500][y+500]=true;
    		X+=500,Y+=500;
    		printf("%d\n",BFS());
    	}
    	return 0;
    }

**Poj 2251 Dungeon Master**

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=50;
    
    struct Point
    {
    	int x,y,z,step;
    };
    
    int visit[N][N][N],X,Y,Z,x,y,z;
    int L,R,C;
    int dx[]={1,-1,0,0,0,0};
    int dy[]={0,0,1,-1,0,0};
    int dz[]={0,0,0,0,1,-1};
    
    int OK (int x,int y,int z)
    {
    	return x>=1 && x<=R && y>=1 && y<=C && z>=1 && z<=L;
    }
    
    void Input ()
    {
    	char str[N];
    	memset(visit,true,sizeof(visit));
    	for (int k=1;k<=L;k++) for (int i=1;i<=R;i++)
        {
            scanf("%s",str+1);
            for (int j=1;j<=C;j++)
            {
                if (str[j]=='.')
                    visit[i][j][k]=false;
                else if(str[j]=='S')
    				x=i,y=j,z=k;
                else if(str[j]=='E')
                {
                    X=i,Y=j,Z=k;
                    visit[i][j][k]=false;
                }
            }
        }
    }
    
    int BFS ()
    {
    	Point top,t;
    	queue <Point> Q;
    	int time=9999;
    	top.step=0;
    	top.x=x;
    	top.y=y;
    	top.z=z;
    	Q.push(top);
    	visit[top.x][top.y][top.z]=true;
    	while (Q.empty()==false)
    	{
    		top=Q.front();
    		Q.pop();
    		if (top.x==X && top.y==Y && top.z==Z)
    		{
    			time=top.step;
    			break;
    		}
    		for (int i=0;i<6;i++)
    		{
    			t.x=top.x+dx[i];
    			t.y=top.y+dy[i];
    			t.z=top.z+dz[i];
    			t.step=top.step+1;
    			if (OK(t.x,t.y,t.z) && visit[t.x][t.y][t.z]==false)
    			{
    				visit[t.x][t.y][t.z]=true;
    				Q.push(t);
    			}
    		}
    	}
    	return time;
    }
    
    int main ()
    {
    	while (scanf("%d%d%d",&L,&R,&C) && (L||R||C))
    	{
    		Input();
    		int ans=BFS();
    		if (ans==9999)
    			printf("Trapped!\n");
    		else
    			printf("Escaped in %d minute(s).\n",ans);
    	}
    	return 0;
    }