题目描述

n*m二维数组表示迷宫，0表示可以走的路，1表示不可通过
请问从左上角到右下角，至少需要移动多少次

输入格式
第一行整数n,m
接下来n行包含m个数，表示迷宫

样例

5 5
0 1 0 0 0 
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

BFS

题目中最少对应想到使用BFS（每一个边长都相同）
dfs对应多少种

bfs基于队列实现

BFS模板

struct Node{...};
queue<Node>q;
bool sta[][]


int bfs(){
    //第一个元素入队，修改第一个元素状态值
     while(...){  //队列不为空
         //保存当前队首元素（做变换）
         //队首出队

         for(...){//遍历每一种情况
            //计算下一步坐标
            if(...) continue;  //判别不合法情况

            //合法则入队
            //更改其状态值

             if(...){ //终点判别
                 return;
             }

         }
     }
}

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=200;
int n,m;
int mp[N][N];
int d[N][N];  //走到每个点时走的距离，初始化为-1代表未走过该点（类似于dfs中的状态数组）
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

struct Node{
    int x;
    int y;
};


queue<Node> q;


int bfs(){
    //起点入队，起点距离为0
    q.push({0,0});
    d[0][0]=0;

    //队不为空
    while(!q.empty()){
        //队首出队
        Node t=q.front();
        q.pop();

        //遍历每种可能
        for(int i=0;i<4;i++){
            int ix=t.x+dx[i],iy=t.y+dy[i];

            //排除不合法情况
            if(ix<0||iy<0||ix>=n||iy>=m||d[ix][iy]!=-1||mp[ix][iy]==1)
                continue;

            //入队
            q.push({ix,iy});
            d[ix][iy]=d[t.x][t.y]+1; //距离更新
            if(ix==n-1&&iy==m-1)
                return d[ix][iy];
        }

    }

}


int main(){
    cin>>n>>m;
    memset(d,-1,sizeof(d));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mp[i][j];
        }
    }
    cout<<bfs();

    return 0;
}