在洛谷上遇到一道01迷宫问题(【P1141】01迷宫)
队列函数没问题,测试过的,只需要检查主函数和全局变量。思路是利用队列进行广度优先搜索,并在每次循环后记忆能到达的格子,计入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);
}
}
}