dfs

bfs

函数写法

1. 定义对头和队尾hh,tt
2. 定义x和y的位置,用一个二元组去存q[N*N]
3. 将d数组全部初始化为-1
4. 开头的d[0][0]初始化为0
5. 写偏移量
6. 判断队头和队尾
7. auto一个t，存q还没有走的值
8. 预处理各个方向的偏移量
9. 判断如果合法就存进去

   #include<bits/stdc++.h>
   using namespace std;
   typedef pair<int,int> PII;
   
   const int N = 110;
   int n,m;
   int g[N][N],d[N][N];//g数组存图，d数组存的是每一个点到起点的距离
   PII q[N*N];
   
   int bfs(){
       int hh = 0;//队头
       int tt = 0;//队尾
       q[0] = {0,0};//xy的坐标
       memset(d,-1,sizeof d);
       d[0][0] = 0;//距离原点的距离为0
       int dx[4] = {-1,0,1,0};
       int dy[4] = {0,1,0,-1};
       
       while(hh <= tt){
           auto t = q[hh++];
           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] == -1){
                   d[x][y] = d[t.first][t.second] + 1;
                   q[++tt] = {x,y};
               }
           }
       }
       return d[n-1][m-1];
   }
   
   
   int main(void){
       cin >> n >> m;
       for(int i = 0;i < n;i++){
           for(int j = 0;j < m;j++){
               cin >> g[i][j];
           }
       }
       cout << bfs() << endl;
   }