532 - Dungeon Master

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shafkat amin
New poster
Posts: 1
Joined: Thu Nov 14, 2002 4:08 pm
Location: Bangladesh

532 - Dungeon Master

Post by shafkat amin » Thu Nov 14, 2002 4:32 pm

i dont know why this code is getting WA.. can any one help...
i am still locked in the dungeon.....

MY CODE::


/**************************/
#include<stdio.h>

char dung[1000][35];
long vis[1000][35];

long l,r,c;
long sr,sc;

long maxrow;

struct point{
long row;
long col;
};

point Q[1000];
long time[1000];
long top;
long head;

long bfs()
{
long i,y,flag;
point x;
point adj[10];
vis[sr][sc]=1;
time[0]=0;
head=0;
long pt;
while(top!=head)
{
y=time[head];
x=Q[head++];
adj[0].row=x.row-1;
adj[0].col=x.col;

adj[1].row=x.row+1;
adj[1].col=x.col;

adj[2].row=x.row;
adj[2].col= x.col+1;

adj[3].row=x.row;
adj[3].col=x.col-1;

adj[4].row=x.row+r;
adj[4].col=x.col;

adj[5].row=x.row-r;
adj[5].col=x.col;

for(i=0;i<6;i++)
{
flag=0;
if(adj.row<0 || adj.row>=maxrow)
flag=1;
else if(adj.col<0 || adj.col>=c)
flag=1;
if(flag==0)
if(dung[adj.row][adj.col]=='.' || dung[adj.row][adj.col]=='E' )
{
if(vis[adj.row][adj.col]==0)
{
pt=time[top]=y+1;
Q[top++]=adj[i];
vis[adj[i].row][adj[i].col]=1;
if(dung[adj[i].row][adj[i].col]=='E')
return pt;
}
}
}
}
return -1;
}



void main()
{
long i,j,k;
long x;

while(1)
{
scanf("%ld %ld %ld",&l,&r,&c);
getchar();
if(l==0 && r==0 && c==0)
break;
for(i=0;i<l;i++)
{
for(j=0;j<r;j++)
{
for(k=0;k<c;k++)
{
scanf("%c",&dung[(i*r)+j][k]);
vis[(i*r)+j][k]=0;
if(dung[(i*r)+j][k]=='S')
{
sr=(i*r)+j;
sc=k;
}
}
getchar();
}
getchar();
}
maxrow=r*l;
top=0;head=0;
Q[top].row=sr;
Q[top++].col=sc;

x=bfs();
if(x==-1)
printf("Trapped!\n");
else
printf("Escaped in %ld minute(s).\n",x);

}
}

dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC

532 Dungeon Master

Post by dabendan » Thu Nov 21, 2002 2:02 am

I got wa so many times.
I hope someone can give me an example to help me debug my program.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Nov 26, 2002 12:45 am

It's a simple, almost text-book BFS, maybe you're using the wrong algo? If it passes for the sample cases, then it should work..

dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC

Post by dabendan » Wed Nov 27, 2002 10:29 am

It passed for the sample cases, but I still get WA.
I use BFS and can't find any problem.

dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC

Post by dabendan » Wed Nov 27, 2002 10:51 am

Here is my code.
My output format is wrong?
My algorithm is wrong?
I can't figure out.
[c]#include <stdio.h>
#include <stdlib.h>
#define MAX 32767

long l,r,c;
char a[32][32][32];

long queue[MAX][4];
long left,right;
int Add_queue(long,long,long,long);
int Get_queue(long *);

int main()
{
void Input();
void BFS();
while(1){
left=right=0; /* set queue to empty */
Input();
BFS();
}
}

void BFS()
{
long v[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
long n[4];
long i,temp;

while(left!=right)
{
Get_queue(n);
if(a[n[0]][n[1]][n[2]]==2)
{
printf("Escaped in %ld minute(s).\n",n[3]);
return;
}
a[n[0]][n[1]][n[2]]=3;
for(i=0;i<6;i++)
{
temp=a[n[0]+v[0]][n[1]+v[1]][n[2]+v[2]];
if(temp==0 || temp==2)
{
Add_queue(n[0]+v[0],n[1]+v[1],n[2]+v[2],n[3]+1);
}
}
}
printf("Trapped!\n");
}

int Add_queue(long g,long h,long i,long level)
{
if(right==left-1)
return(0);
queue[right][0]=g;
queue[right][1]=h;
queue[right][2]=i;
queue[right][3]=level;
right=(right+1)%MAX;
return(1);
}

int Get_queue(long *v)
{
int i;
if(left==right)
return(0);
for(i=0;i<4;i++)
v=queue[left];
left=(left+1)%MAX;
return(1);
}

void Input()
{
long i,j,k;
char str[32];

for(i=0;i<32;i++)
for(j=0;j<32;j++)
for(k=0;k<32;k++)
a[j][k]=1;
fscanf(stdin,"%ld %ld %ld",&l,&r,&c);
if(l==0 && r==0 && c==0)
exit(0);
for(i=0;i<l;i++)
{
for(j=0;j<r;j++)
{
fscanf(stdin,"%s",str);
for(k=0;k<c;k++)
{
switch(str[k])
{
case '#':
a[i+1][j+1][k+1]=1;
break;

case 'S':
Add_queue(i+1,j+1,k+1,0);
case '.':
a[i+1][j+1][k+1]=0;
break;

case 'E':
a[i+1][j+1][k+1]=2;
break;
}
}
}
}
}[/c]

dabendan
New poster
Posts: 13
Joined: Mon May 06, 2002 4:05 pm
Location: ROC

Post by dabendan » Fri Dec 13, 2002 12:49 pm

my program don't work when the 3 numbers in the input are even and the maze is empty.
ex:
2 2 2
S.
..

..
.E

however I fixed it and got ac.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

P-532

Post by Red Scorpion » Sat Feb 08, 2003 8:02 am

Hi,

Use This Test Case :
Sample Input:

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

4 4 5

#####
#####
##.##
##...

#####
###S#
#.#.#
#....

#####
#####
#.###
####E

#####
#...#
...##
#....

1 2 2

##
SE

3 3 3

###
#E#
#.#

#..
.##
.#.

...
...
..S

5 2 2

##
##

#.
..

.S
..

..
..

.E
..

2 1 1

S

E

1 1 2

SE

1 5 5

#####
S####
....#
####E
##...

2 3 3

#.E
...
...

...
...
..S

2 4 4

####
#S##
....
###.

####
.###
.###
.E..

2 5 5

#####
#S..#
..#..
.###.
.###.

#####
#####
#####
#####
..E..

0 0 0

Output :
Escaped in 11 minute(s).
Trapped!
Escaped in 4 minute(s).
Escaped in 1 minute(s).
Trapped!
Escaped in 2 minute(s).
Escaped in 1 minute(s).
Escaped in 1 minute(s).
Trapped!
Escaped in 3 minute(s).
Escaped in 5 minute(s).
Escaped in 7 minute(s).

Hope this helps.
GOOD LUCK,
RED SCORPION :lol:

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Feb 08, 2003 6:26 pm

Perhaps make your queue bigger? it's suppose to be 50 * 50 * 50..

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

it's tle that annoied me very much

Post by anupam » Mon Mar 17, 2003 7:24 am


all of you said about gettong wa..
but i have tried the problem several time using dfs/ recursion and i tried to minimize the recursion as possible..
but till today i got tle from the judge..
is there any second algorithm exist?
if yes then please let me know..
if you can't understand i will paste my code here...
but if any algorithm exists please let me know....
please....
your help is needed..
thanks and have a good day..
--anupam
:oops: :oops: :oops: :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Mar 17, 2003 10:31 am

Try to use BFS instead of DFS
:lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol:

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

532 - Dungeon Master OLE

Post by playerX » Fri Sep 12, 2003 8:43 pm

I'm getting time(* EDITED -> Not Time, I mean OUTPUT *) limit exceeded... could anyone tell me why my program is getting into an infinite loop? thanks in advance.

[c]
#include <stdio.h>

#define MAX 30
#define MAXQ MAX*3

unsigned char maze[MAX][MAX][MAX];
unsigned char visited[MAX][MAX][MAX];
unsigned short int tm[MAX][MAX][MAX];

char startx,starty,startz,endx,endy,endz,xbound,ybound,zbound;

struct cords {
unsigned char x,y,z;
};

void bfs (char x, char y, char z, char xe, char ye, char ze) {
struct cords queue[MAXQ];
int head=0,tail=0,vx,vy,vz;
tm[z][y][x]=0;
memset(visited,0,sizeof(visited));
queue[tail].x=x;
queue[tail].y=y;
queue[tail].z=z;
tail++;
while (head != tail) {
vx=queue[head].x;
vy=queue[head].y;
vz=queue[head].z;
head++;
if (xe == vx && ye == vy && ze == vz) return;
if (vz+1 < zbound && maze[vz+1][vy][vx] == '.' && visited[vz+1][vy][vx] == 0) {
visited[vz+1][vy][vx]=1;
tm[vz+1][vy][vx]=tm[vz][vy][vx]+1;
queue[tail].x=vx;
queue[tail].y=vy;
queue[tail].z=vz+1;
tail++;
}
if (vz-1 >= 0 && maze[vz-1][vy][vx] == '.' && visited[vz-1][vy][vx] == 0) {
visited[vz-1][vy][vx]=1;
tm[vz-1][vy][vx]=tm[vz][vy][vx]+1;
queue[tail].x=vx;
queue[tail].y=vy;
queue[tail].z=vz-1;
tail++;
}
if (vy+1 < ybound && maze[vz][vy+1][vx] == '.' && visited[vz][vy+1][vx] == 0) {
visited[vz][vy+1][vx]=1;
tm[vz][vy+1][vx]=tm[vz][vy][vx]+1;
queue[tail].x=vx;
queue[tail].y=vy+1;
queue[tail].z=vz;
tail++;
}
if (vy-1 >= 0 && maze[vz][vy-1][vx] == '.' && visited[vz][vy-1][vx] == 0) {
visited[vz][vy-1][vx]=1;
tm[vz][vy-1][vx]=tm[vz][vy][vx]+1;
queue[tail].x=vx;
queue[tail].y=vy-1;
queue[tail].z=vz;
tail++;
}
if (vx+1 < xbound && maze[vz][vy][vx+1] == '.' && visited[vz][vy][vx+1] == 0) {
visited[vz][vy][vx+1]=1;
tm[vz][vy][vx+1]=tm[vz][vy][vx]+1;
queue[tail].x=vx+1;
queue[tail].y=vy;
queue[tail].z=vz;
tail++;
}
if (vx-1 >= 0 && maze[vz][vy][vx-1] == '.' && visited[vz][vy][vx-1] == 0) {
visited[vz][vy][vx-1]=1;
tm[vz][vy][vx-1]=tm[vz][vy][vx]+1;
queue[tail].x=vx-1;
queue[tail].y=vy;
queue[tail].z=vz;
tail++;
}
}
}

int main () {
int i,j,k;
while (1) {
fscanf(stdin,"%d %d %d\n",&zbound,&ybound,&xbound);
if (xbound == 0 && ybound == 0 && zbound == 0) break;
for (k=0;k<zbound;k++) {
for (i=0;i<ybound;i++) {
gets(maze[k]);
j=0;
while (maze[k][j] != '\0') {
if (maze[k][j] == 'S') {
startx=j;
starty=i;
startz=k;
maze[k][j]='.';
}
if (maze[k][j] == 'E') {
endx=j;
endy=i;
endz=k;
maze[k][j]='.';
}
j++;
}
}
fscanf(stdin,"\n");
}
bfs(startx,starty,startz,endx,endy,endz);
if (visited[endz][endy][endx]) fprintf(stdout,"Escaped in %d minute(s).\n",tm[endz][endy][endx]);
else fprintf(stdout,"Trapped!\n");
}
}[/c]
Last edited by playerX on Sat Sep 13, 2003 7:18 pm, edited 1 time in total.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sat Sep 13, 2003 2:03 am

I can give you some input/output...
Mail me.

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post by playerX » Sat Sep 13, 2003 7:16 pm

Thanks a lot Dmytro, but I already tested it with inputs I found on the board and I'm pretty sure everything is correct about the algo (maybe there's a small mistake, I need some extreme boundary input).

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sat Sep 13, 2003 7:30 pm


chaoshidai
New poster
Posts: 1
Joined: Fri Aug 01, 2003 6:27 pm

Post by chaoshidai » Fri Jan 30, 2004 8:15 pm

[/pascal][/code]
program p532;
{$APPTYPE CONSOLE}
uses SysUtils;

const f:array[1..6,1..3]of longint=((0,1,0),(0,-1,0),(1,0,0),(-1,0,0),(0,0,1),(0,0,-1));

var st:array[1..50,1..50,1..50]of char;
b:array[1..50,1..50,1..50]of 0..1;
m:array[1..50,1..50,1..50]of longint;
l,r,c,i,j,k,si,sj,sk:longint;
s:string;

procedure search(i,j,k:longint);
var ii,temp,min:longint;t:boolean;

procedure tf(i,j,k:longint);
begin
t:=false;
if (i<1)or(i>l)or(j<1)or(j>r)or(k<1)or(k>c) then exit;
if st[i,j,k]='#' then exit;
if b[i,j,k]=1 then exit;
t:=true;
end;

begin
if st[i,j,k]='E' then begin m[i,j,k]:=1;exit;end;
min:=-1;
for ii:=1 to 6 do
begin
tf(i+f[ii,1],j+f[ii,2],k+f[ii,3]);
if t then
begin
if m[i+f[ii,1],j+f[ii,2],k+f[ii,3]]=-1
then
begin
b[i+f[ii,1],j+f[ii,2],k+f[ii,3]]:=1;
search(i+f[ii,1],j+f[ii,2],k+f[ii,3]);
b[i+f[ii,1],j+f[ii,2],k+f[ii,3]]:=0;
end;
temp:=m[i+f[ii,1],j+f[ii,2],k+f[ii,3]];
if (temp<>0)and((min=-1)or(temp<min))
then min:=temp;
end;
end;
m[i,j,k]:=min+1;
end;


begin
readln(l,r,c);
repeat
si:=0;sj:=0;sk:=0;
for i:=1 to l do
begin
for j:=1 to r do
begin
readln(s);
while s='' do readln(s);
for k:=1 to c do
begin
st[i,j,k]:=s[k];
if st[i,j,k]='S' then begin si:=i;sj:=j;sk:=k;end;
end;
end;
readln;
end;
fillchar(b,sizeof(b),0);
fillchar(m,sizeof(m),-1);
b[si,sj,sk]:=1;
if si*sj*sk<>0 then search(si,sj,sk);
if si*sj*sk=0 then writeln('Trapped!')
else
if m[si,sj,sk]<1
then writeln('Trapped!')
else writeln('Escaped in ',m[si,sj,sk]-1,' minute(s).');
readln(l,r,c);
until (l=0) and (r=0) and (c=0);
end.


I use dfs+remember,but also wrong answer.
anyone can help me?

Post Reply

Return to “Volume 5 (500-599)”