/ Vijos / 讨论 / 图论 /

求助bfs 写迷宫问题!答案一直不对啊,不知道为啥

//    //简单迷宫问题:来自《算法竞赛入门经典》
/*输入: 迷宫大小的行n,列m
                 起点 stax,stay
                 终点 aix,aiy
                 输入迷宫:1为障碍,0可通过
     输出:终点处的最短路径 dist[aix][aiy]
     6 5
     0 0
     5 4
     0 0 1 0 0
     0 1 0 0 0
     0 1 0 1 1
     0 1 0 0 0
     0 0 0 1 0
     0 0 0 0 0    */
#include <stdio.h>
#define MAX 1000
int m,n;
int vis[MAX][MAX],fa[MAX][MAX],dist[MAX][MAX],maze[MAX][MAX];
int q[MAX*MAX];
int dx[4],dy[4];
void bfs(int x,int y)
{
    int nx,ny;
    int u,v,d,rear=0,front=0;
    u=x*m+y;
    q[rear++]=u;           //入队
    vis[x][y]=1;
    fa[x][y]=u;
    dist[x][y]=0;
    while(front<rear)
    {
        v=q[front++];//出队
        x=v/m;
        y=v%m;
        for(d=0;d<4;d++)
        {
            nx=x+dx[d];
            ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]&&vis[nx][ny]==0)
            {
                q[rear++]=nx*m+ny;
                vis[nx][ny]=1;
                fa[nx][ny]=v;
                dist[nx][ny]=dist[x][y]+1;
            }

        }
    }
}


int main()
{
    int aix,aiy,stax,stay;
    int i,j;
    scanf("%d %d",&n,&m);
    scanf("%d",&stax);
    scanf("%d",&stay);
        scanf("%d",&aix);
            scanf("%d",&aiy);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&maze[i][j]);
        }
    }
    dx[0]=0,dy[0]=1;
    dx[1]=1,dy[1]=0;
    dx[2]=0,dy[2]=-1;
    dx[3]=-1,dy[3]=0;
    bfs(stax,stay);
    printf("%d\n",dist[aix][aiy]);
    return 0;
}

3 条评论

  • 1