上单塞娜零杠九
2022-01-17 16:38
采纳率: 0%
浏览 40

关于01迷宫bfs问题的一些疑惑

在洛谷上遇到一道01迷宫问题(【P1141】01迷宫)

img


img

队列函数没问题,测试过的,只需要检查主函数和全局变量。思路是利用队列进行广度优先搜索,并在每次循环后记忆能到达的格子,计入ans数组中,减小复杂度。
(通过40%用例) RE 4个 WA 2个

#include <iostream>
#include <malloc.h>
#include <string.h>
char s[1005][1005];  //迷宫 
int visit[1005][1005]={0};  //访问标记 
int ans[1005][1005]={0};    //记忆数组,记忆每格的答案 
typedef struct{
    int a;
    int b;
}ffa;  //坐标:a行b列 
typedef ffa elemtype;
typedef struct{
    elemtype *top;
    elemtype *base;
    int size;
    elemtype *a;
}quene;
ffa locate[100005];
void create(quene &q){  //创建队列 
    q.base=(elemtype*)malloc(1000*sizeof(elemtype));
    q.top=q.base;
    q.size=0;
    q.a=q.base;
}
elemtype front(quene &q){   //返回队首元素 
    elemtype e;
    e=*q.base;
    return e;
}
elemtype back(quene &q){   //返回队尾元素 
    elemtype e;
    e=*(q.top-1);
    return e;
}
void pop(quene &q){   //弹出队首元素 
    q.base++;
    q.size--;
}
void push(quene &q, elemtype e){   //添加元素 
    *q.top=e;
    q.top++;
    q.size++;
}
int size(quene &q){    //返回队列元素数量 
    return q.size;
}
int empty(quene &q){   //判断队列是否为空
    if(q.size==0) return 1;
    return 0;
}
void _free(quene &q){   //清空队列
    while(q.top!=q.base){    
        q.top--;
    }
        q.size=0;
}
int different(ffa w1, ffa w2){ //判断两个格子数值是否不同,若不同返回1 
    if(s[w1.a][w1.b]!=s[w2.a][w2.b]) return 1;
    return 0;
}
int main(){
    int m,n,x,y;
    quene q;
    create(q);
    int total;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("\n");
        for(int j=1;j<=n;j++){
            scanf("%c",&s[i][j]);
        }
    }
    scanf("\n");
    //for(int i=1;i<=n;i++){
    //    for(int j=1;j<=n;j++){
    //        printf("%c",s[i][j]);
    //    }
    //}
    for(int i=1;i<=m;i++){
        scanf("%d%d",&locate[i].a,&locate[i].b);
    }
    for(int i=1;i<=m;i++){
    if(ans[locate[i].a][locate[i].b]!=0) printf("%d\n",ans[locate[i].a][locate[i].b]);
    else{
        total=0;memset(visit,0,sizeof(visit)); //初始化 
        push(q,locate[i]);visit[locate[i].a][locate[i].b]=1;
        ffa point1,point2,point3,point4; //周围四个点 
        while(!empty(q)){   //(x,y)是队头元素,先令(x,y)周围符合条件的点入队列,再让(x,y)出队列 
            x=front(q).a;y=front(q).b; //队头元素的x,y坐标 
            if(x>1){
                point1.a=x-1;point1.b=y;
                if(visit[point1.a][point1.b]==0&&different(point1,front(q))){
                    push(q,point1);visit[point1.a][point1.b]=1;
                }  //若未被访问,则访问之,并进队列,同时上访问标记,下面类似处理 
            }
            if(x<n){
                point2.a=x+1;point2.b=y;
                if(visit[point2.a][point2.b]==0&&different(point2,front(q))){
                    push(q,point2);visit[point2.a][point2.b]=1;
                }
            }
            if(y>1){
                point3.a=x;point3.b=y-1;
                if(visit[point3.a][point3.b]==0&&different(point3,front(q))){
                    push(q,point3);visit[point3.a][point3.b]=1;
                }
            }
            if(y<n){
                point4.a=x;point4.b=y+1;
                if(visit[point4.a][point4.b]==0&&different(point4,front(q))){
                    push(q,point4);visit[point4.a][point4.b]=1;
                }
            }
            total++;
            pop(q);
        }
        for(int j=1;j<=n;j++){    //记忆操作 
            for(int k=1;k<=n;k++){//若本轮被访问过,则答案为total,减少后续不必要的循环 
                if(visit[j][k]==1) ans[j][k]=total;
            }
        }
        printf("%d\n",total);
    }
    }
}

1条回答 默认 最新

相关推荐 更多相似问题