AcWing 844. 走迷宫

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 844. 走迷宫原题链接简单

作者：

Ni , 2019-11-01 18:16:10 , 所有人可见 , 阅读 7418

43

13

走迷宫BFS的基本应用

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110;


int g[N][N];    //存储地图
int d[N][N];    //标记搜索到的点的距离
int n,m;        //地图的长宽

struct elem{
    int x;
    int y;
};

struct elem q[N*N]; //队列用于BFS操作
int bfs()
{
    memset(d,-1,sizeof d);  //初始化d

    int hh=0,tt=0;
    d[0][0]=0;  //左上角第一个点开始搜索

    q[hh]={0,0};    //将第一个点入队

    int dx[4]={-1,0,1,0};   //方向盘用于对个方向进行尝试
    int dy[4]={0,-1,0,1};

    while(hh<=tt)   //
    {
        struct elem j=q[hh++];  //获取队头元素 然后将其出队

        for(int i=0;i<4;i++)
        {
            int x=j.x+dx[i];
            int y=j.y+dy[i];
            if(x>=0&&y>=0&&x<n&&y<m&&g[x][y]==0&&d[x][y]==-1)     //点未出界 该点可走 且未走过
            {
                d[x][y]=d[j.x][j.y]+1;
                q[++tt]={x,y};
            }
        }
    }

    return    d[n-1][m-1];
}
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;
    return 0;

}

13 评论

h闵 7个月前

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
// #include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int g[N][N];
int d[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int n,m;

// vector<PII> q;
PII q[N * N];

int dfs()
{
    int hh = 0,tt = 0;
    q[hh] = {0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;

    while(hh <= tt)
    {
        PII t = q[hh];
        hh++;

        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[++tt] = {x,y};
            }
        }
    }

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

int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }

    printf("%d\n",dfs());

    return 0;
}

为什么vector[HTML_REMOVED] q;就会报错
PII q[N * N];这样才可以啊，我不理解这个是为什么，原则上不都是可以的吗?