bfs模板

bfs算法模板

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int > PII;
const int N=1e2+7;
int g[N][N];
int d[N][N];


int n,m;
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
int bfs()
{


        queue<PII> q;
   
       q.push({0,0}); // STRATR OF  DATA;
 
      
       memset(d,-1,sizeof d);
       d[0][0]=0;
       while(q.size())
         {    PII t=q.front();  //get the  head of t;  取队头的元素
              q.pop();  //POP 
              for(int i=0;i<4;i++)
                {    
                    int x=t.first+dx[i];
                    int y=t.second+dy[i];


                    //判断是否越界
                    if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-W1)
                             {    d[x][y]=d[t.first][t.second]+1;
                                   q.push({x,y});
                                   cout<<d<<endl;
                                  

                             }


                }
          

             
 
            
         }

   return d[n-1][m-1];
}




int main()
{      
      cin>>n>>m;
      for(int i=0;i<n;i++)
        {

        for(int j=0;j<n;j++) 
             {

                 cin>>g[i][j];
           }

        }
     
      cout<<bfs()<<endl;
  



}

为什么使用队列

代码思路

首先从起点开始遍历，将坐标(0,0)放入队列，然后进行从0,0开始bfs宽搜，先将起点(0,0)出队，再用方向数组向所有点进行尝试，如果该点是可走的，而且没有走过，那么该点符合要求，此时该点的距离为上一个点对应的距离＋1，并且将该点加入队列。队列符合先进先出的特点，因此一定不会重复访问，距离在后的点一定在后面。