HUST Online Judge WebBoard
Problem 3968 >> 按书上算法写的,不知道为啥一直错误50%
201803010218 @ 2019-10-30 20:46:24
[ Quote ] [ Edit ] [ Delete ] 1#
#include<stdio.h>
#include"stdlib.h"
#include<string.h>

typedef struct
{
int i,j;
int pre;
} box;

typedef struct
{
box a[12100];
int front,rear;
} K;

K *init()
{
K *p;
p=(K*)malloc(sizeof(K));
p->front=p->rear=-1;
return p;
}

int empty(K *p)
{
if(p->front==p->rear)
return 0;
else
return 1;
}

void in(K *p,box e)
{
p->rear++;
p->a[p->rear].i=e.i;
p->a[p->rear].j=e.j;
p->a[p->rear].pre=e.pre;
}

void out(K *p,int *w,int *s)
{
p->front++;
*w=p->a[p->front].i;
*s=p->a[p->front].j;
}

void print(K *p,int front)
{
int k=front;
int j,t=0;
printf("\n");
do
{
j=k;
k=p->a[k].pre;
p->a[j].pre=-1;
} while(k!=0);
printf("开始输出路径\n");
k=0;
while(k<12100)
{
if(p->a[k].pre==-1)
{
t++;
printf("(%d %d) ",p->a[k].i,p->a[k].j);
if(t%5==0)
printf("\n");
}
k++;
}
printf("输出总步数:\n\n%d\n",t-1);
}

int main()
{
int i,j,n,m,q,s1,s2,e1,e2;
int flag=-1;
char h[110][110];
scanf("%d",&q);
while(q>0)
{
//*************************************************************************//
scanf("%d %d",&m,&n);
getchar();
for(i=1;i<m+1;i++) //输入迷宫内容
{
for(j=1;j<n+2;j++)
{
scanf("%c",&h[i][j]);
}
}
for(i=0;i<m+2;i++) //给迷宫加一个围墙
{
for(j=0;j<n+2;j++)
{
if(i==0||j==0||j==n+1||i==m+1)
{
h[i][j]='#';
}
}
}
printf("打印加了围墙的迷宫图\n");
for(i=0;i<m+2;i++) //输出迷宫
{
for(j=0;j<n+2;j++)
{
if(h[i][j]=='S')
{
s1=i;
s2=j;
}
if(h[i][j]=='E')
{
e1=i;
e2=j;
}
printf("%c",h[i][j]);
if(j==n+1)
{
printf("\n");
}
}
}
//************************************************************************//
printf("\n(%d %d) (%d %d)\n",s1,s2,e1,e2);
K *p;
box e;
int t,v,k,*w,*s;
w=&e.i;
s=&e.j;
p=init();
e.i=s1;
e.j=s2;
e.pre=-1;
in(p,e);
h[s1][s2]='o'; ///起点入队
while(empty(p)!=0)
{

out(p,w,s);
i=*w;
j=*s;
printf("编号:%d ",p->front);
printf("位置(%d %d) 此位置来源:%d\n",*w,*s,p->a[p->front].pre);
if(i==e1&&j==e2)
{
print(p,p->front);
flag=0;
break;
}
for(k=0; k<4; k++)
{
switch(k)
{
case 0:
t=i-1;
v=j;
break;
case 1:
t=i;
v=j+1;
break;
case 2:
t=i+1;
v=j;
break;
case 3:
t=i;
v=j-1;
break;
}
if(h[t][v]=='-'||h[t][v]=='E') //四个方向进行查询,符合条件就入队,并使其值为o防止重复查询
{
e.i=t;
e.j=v;
e.pre=p->front; //pre标记位置来源
in(p,e);
h[t][v]='o';
}
}
}
if(flag==-1)
{
printf("-1\n");
}
q--;
}
return 0;
}
201803010218 @ 2019-10-30 20:47:03
[ Quote ] [ Edit ] [ Delete ] 2#
求大佬帮忙看看,感谢了~
201803140220 @ 2019-10-31 18:11:37
[ Quote ] [ Edit ] [ Delete ] 3#
在你的主函数内
参数 flag=-1 定义在了 while 循环外
因此后面在多次运行循环时
flag的值就可能不会再变化
201803010218 @ 2019-10-31 18:47:06
[ Quote ] [ Edit ] [ Delete ] 4#
嗷嗷,才发现这个,刚刚改了一下,不过还是错误50%。。。。
是不是还有其他问题啊,感觉好奇怪......
201803140220 @ 2019-10-31 19:06:21
[ Quote ] [ Edit ] [ Delete ] 5#
呃。。。
还有一点:题目的要求是 1<=N,M<=100;
也就是总计可能会有10000个路径点
你的 box 定义的 a[ ] 数组在讨论板里是正确的
而后面提交到OJ的几组里数组大小没改
201803010218 @ 2019-10-31 19:50:41
[ Quote ] [ Edit ] [ Delete ] 6#
噢噢噢噢,犯傻了,讨论板这个是之前改好的最后一版。。。。
刚刚拿的以前提交的版本在改flag去了
现在问题已经解决了,再次感谢大佬相助