Java教程

BFS广度优先搜索

本文主要是介绍BFS广度优先搜索，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：

1.多条路一起走，知道有一条路走到终点，就返回步数

2.标记所有走过的格子为2，终点为3

3.以当前格子(now)为中心，判断上下左右格子是否符合条件（视具体情况而定），用一个新的二位数组来模拟移动

4.使用栈(queue)来存储信息，并进行判断，和改变当前格子信息

5.还可以用于解决连通问题

模板;

(23条消息) C++算法——BFS（图解）_隰有游龙的博客-CSDN博客_c++bfs

#include<bits/stdc++.h>
using namespace std;
long long Map[5][5];//map是stl的一个结构，不能直接做变量名 
long long Dir[4][2]={-1,0,1,0,0,1,0,-1};
struct node
{
    int x;
    int y;
    int step;
}；//可以这种定义方法，要记住 
Node now,next;
int bfs(int a,int b)
{
    queue<node>q;
    now.x=a;
    now.y=b;
    now.step=0;
    Map[a][b]=2;//记录已经走过的点 
    q.push(now);
    while(!q.empty())
    {
          now=q.front();
          q.pop();//有push就有pop,必须清内存 
          for(int i=0;i<4;i++)
          {
              int xx=now.x+Dir[i][0];
              int yy=now.y+Dir[i][1];
              if(xx>=0&&xx<5&&yy>=0&&yy<5&&Map[xx][yy]!=1&&Map[xx][yy]!=2)
              {
                  next.x=xx;
                  next.y=yy;
                  next.step=now.step+1;
//把上一步标为已经走了，而不是当前的
//到最后一步时，当前值变为2，把3覆盖了
Map[now.x][now.y]=2;
                if(Map[xx][yy]==3)
                return next.step;
                q.push(next); 
            }
          }//打印每一步 
          for(int i=0;i<5;i++)
          {
              for(int j=0;j<5;j++)
          cout<<Map[i][j];
          cout<<endl;
          }
          cout<<endl;
    }
    return -1;//走不通就返回-1 
}
 int main()
 {
     for(int i=0;i<5;i++)
     for(int j=0;j<5;j++)
    {
        cin>>Map[i][j];
     } 
     Map[4][4]=3;
     long long ans;
     ans=bfs(0,0);
     cout<<ans<<endl;
     return 0;
 }

骑士招式

1915 -- 骑士招式 (poj.org)

优化前

#include<bits/stdc++.h>
using namespace std;
long long Map[300][300];
long long Dir[8][2]={-2,-1,-1,-2,1,-2,2,-1,-2,1,-1,2,1,2,2,1};
struct node
{
    int x;
    int y;
    int step;
 }now,next;
 int bfs(long long a,long long b,long long m)
 {
     queue<node>q;
     now.x=a;
     now.y=b;
     now.step=0;
     Map[a][b]=2;
     q.push(now);
     while(!q.empty())
     {
         now=q.front();
         q.pop();
         for(int i=0;i<8;i++)
         {
             int xx=now.x+Dir[i][0];
             int yy=now.y+Dir[i][1];
            if(xx>=0&&xx<m&&yy>=0&&yy<m&&Map[xx][yy]!=2)
            {
                next.x=xx;
                next.y=yy;
                next.step=now.step+1;
                Map[now.x][now.y]=2;
                if(Map[xx][yy]==3) 
                return next.step;
                q.push(next);
            }
         }
     }
     return -1;
 }
 int main()
 {  long long n;
    long count=0,Step[100];
    cin>>n;
    for(int a=0;a<n;a++)
    {
    long long m;
     cin>>m;
     for(int i=0;i<m;i++)
     for(int j=0;j<m;j++)
     {
         Map[i][j]=0;
     }
    long long s1,s2,e1,e2;
    cin>>s1>>s2>>e1>>e2;
    if(s1==e1&&s2==e2)
    {
        Step[count]=0;
        count++;
    }
    else
    {
         Map[e1][e2]=3;
    Step[count]=bfs(s1,s2,m);
    count++;
    }
    }
    for(int i=0;i<count;i++)
    cout<<Step[i]<<endl;
     return 0;
 }

优化后：

#include<bits/stdc++.h>
using namespace std;
long long Map[300][300];
long long Dir[8][2]={-2,-1,-1,-2,1,-2,2,-1,-2,1,-1,2,1,2,2,1};
long long ans,s1,s2,e1,e2;
struct node
{
    int x;
    int y;
    int step;
 }now,next;
 int bfs(long long a,long long b,long long m)
 {
     queue<node>q;
     now.x=a;
     now.y=b;
     now.step=0;
     Map[a][b]=2;
     q.push(now);
     while(!q.empty())
     {
         now=q.front();
         q.pop();
         for(int i=0;i<8;i++)
         {
             int xx=now.x+Dir[i][0];
             int yy=now.y+Dir[i][1];
            if(xx>=0&&xx<m&&yy>=0&&yy<m&&Map[xx][yy]!=2)
            {
                next.x=xx;
                next.y=yy;
                next.step=now.step+1;
                if(xx==e1&&yy==e2)//取消了对now的引用
                return next.step;
                q.push(next);
                Map[xx][yy]=2;
            }
         }
     }
     return -1;
 }
 int main()
 {  long long n;//取消了数组Step
    cin>>n;
    while(n--)//代替for
    {
    long long m;
     cin>>m;
    memset (Map,0,sizeof(Map));//代替for
    cin>>s1>>s2>>e1>>e2;
    if(s1==e1&&s2==e2)
    {
      ans=0;
    }
    else
    {
         Map[e1][e2]=3;
    ans=bfs(s1,s2,m);
    }
    cout<<ans<<endl;
    }
     return 0;
 }

 

 

优化思路：

1.减少变量的定义，特别是数组的使用，以减少空间复杂度

2.减少结构体变量的引用；

For(int i=1;i<n;i++)

的替代为

While(n--)

3.题目中的输出和输入并不是全输出后再全输出

4.主函数中的某些变量定义全局变量更方便

 

 

2.石油储量

 

1562 -- Oil Deposits (poj.org)

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
char Map[maxn][maxn];
int dir[8][2]={{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1},{0,1},{0,-1}};
int m,n,cnt=0;
struct node
{
    int x;
    int y;
}now,next;
void BFS(int x,int y)
{

    now.x=x;
    now.y=y;
    Map[x][y]='*';
    queue<node> q;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int xx=now.x+dir[i][0];
            int yy=now.y+dir[i][1];
            if(xx>=0&&xx<m&&yy>=0&&yy<n&&Map[xx][yy]=='@')
            {                
                Map[xx][yy]='*';
                next.x=xx;
                next.y=yy;
                q.push(next);
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        cnt=0;
        if(m==0)///输入0 0 退出
            break;
        for(int i=0;i<m;i++)
        {
            scanf("%s",Map[i]);
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(Map[i][j]=='@')
                {
                    cnt++;
                    BFS(i,j);
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

 

                                                                     

注意！！！！！！！！！！

如果感觉逻辑都对，检查几遍都没问题，甚至比对都检查不出问题，那就99.99%是细枝末节的问题，比如：

  1. 是否多加了一个分号
  2. 是否把yy写成y
  3. 是否把=写出==

另外：poj不支持万能头

 

这篇关于BFS广度优先搜索的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航