走迷宫

1. 模拟队列

#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int n, m;
int d[N][N];//记录走过的点
int g[N][N];//地图
PII q[N * N];//模拟队列、存放的是 找到的可行的点

int bfs()
{
    int hh = 0;//队列的头部
    int tt = 0;//队列的尾部

    memset(d, -1 ,sizeof d);//标记所有点都未走过

    q[0] = {0, 0};//从第一点开始
    d[0][0] = 0;//表示第一个点 走过

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//用向量的方式表示四个方向

    while(hh <= tt)//只要队列里面有元素 就需要一直找下去
    {
        auto t = q[hh ++];//取出队头元素
        for(int i = 0;i < 4 ;i ++)
        {
            //每次循环都会改变一次方向
            //{x，y}表示的是点
            int x = t.first + dx[i] , y = t.second + dy[i];

            // 判断该方向上是否符合条件
            // x >= 0 && x < n表示在地图内
            // g[x][y] == 0 表示当前点是否可以走
            // d[x][y] == -1 表示当前点还未走过，主要作用是防止往回走
            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];//最后返回终点到起点的距离（因为下标是从 0 开始）
}

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

    cout << bfs() << endl;
}

2. 使用stl

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 110;
typedef pair<int, int> PII;
int g[N][N];
int d[N][N];

int main()
{
    queue <PII> q;
    int n, m;
    cin >> n >> m;

    for(int i = 0;i < n;i ++)
        for(int j = 0;j < m;j ++)
            cin >> g[i][j];

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0;i < 4;i ++)
        {
            int x = t.first + dx[i], 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.push({x,y});
            }
        }
    }

    cout << d[n - 1][m - 1] << endl;

    return 0;
}