## 532 - Dungeon Master

Moderator: Board moderators

lky
New poster
Posts: 21
Joined: Fri Dec 05, 2003 5:59 pm
Contact:

### 532 WA!!!

i tried tonnes of test cases but still WA.....can someone help me?
tell me what is wrong with my source or give me some critical input pls....

{@judge_id: 38587WT 532 Pascal}
program q532;
qx,qy,qz,len:array[1..30000]of longint;
b:array[0..51,0..51,0..51]of boolean;
a:array[0..51,0..51,0..51]of char;
procedure bfs(u:longint);
var v:longint;
begin
b[qx,qy,qz]:=true;
if u>tail
then begin
writeln('Trapped!');
exit
end;
if a[qx,qy,qz]='E'
then begin
writeln('Escaped in ',len,' minute(s).');
exit
end;
if (a[qx+1,qy,qz]<>'#')and(not b[qx[u]+1,qy[u],qz[u]])
then begin
tail:=tail+1;
qx[tail]:=qx[u]+1;
qy[tail]:=qy[u];
qz[tail]:=qz[u];
len[tail]:=len[u]+1
end;
if (a[qx[u]-1,qy[u],qz[u]]<>'#')and(not b[qx[u]-1,qy[u],qz[u]])
then begin
tail:=tail+1;
qx[tail]:=qx[u]-1;
qy[tail]:=qy[u];
qz[tail]:=qz[u];
len[tail]:=len[u]+1
end;
if (a[qx[u],qy[u]+1,qz[u]]<>'#')and(not b[qx[u],qy[u]+1,qz[u]])
then begin
tail:=tail+1;
qx[tail]:=qx[u];
qy[tail]:=qy[u]+1;
qz[tail]:=qz[u];
len[tail]:=len[u]+1
end;
if (a[qx[u],qy[u]-1,qz[u]]<>'#')and(not b[qx[u],qy[u]-1,qz[u]])
then begin
tail:=tail+1;
qx[tail]:=qx[u];
qy[tail]:=qy[u]-1;
qz[tail]:=qz[u];
len[tail]:=len[u]+1
end;
if (a[qx[u],qy[u],qz[u]-1]<>'#')and(not b[qx[u],qy[u],qz[u]-1])
then begin
tail:=tail+1;
qx[tail]:=qx[u];
qy[tail]:=qy[u];
qz[tail]:=qz[u]-1;
len[tail]:=len[u]+1
end;
if (a[qx[u],qy[u],qz[u]+1]<>'#')and(not b[qx[u],qy[u],qz[u]+1])
then begin
tail:=tail+1;
qx[tail]:=qx[u];
qy[tail]:=qy[u];
qz[tail]:=qz[u]+1;
len[tail]:=len[u]+1
end;
end;
begin
while not((x=0)and(y=0)and(z=0)) do
begin
for i:=0 to 51 do
for j:=0 to 51 do
for k:=0 to 51 do
begin
a[i,j,k]:='#';
b[i,j,k]:=false
end;
repeat
if eoln
until not eoln;
for i:=1 to x do
begin
for j:=1 to y do
begin
for k:=1 to z do
end;
end;
for i:=1 to x do
for j:=1 to y do
for k:=1 to z do
begin
if a[i,j,k]='S'
then begin
sx:=i;
sy:=j;
sz:=k;
break
end
end;
tail:=1;
b[sx,sy,sz]:=true;
end
end.

lky
New poster
Posts: 21
Joined: Fri Dec 05, 2003 5:59 pm
Contact:
i finally solved this....this is simply some problem in the operation with the b varibales

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:
hm.. I think using BFS and the Queue method should work.
Do not use DFS.
:: HanWorks ::

smilejfu
New poster
Posts: 5
Joined: Fri Oct 08, 2004 2:29 pm
Contact:

### 532 WA ('ve tried some in/output...T^T)

can someone help ? I can't find the mistake that caused the problem...
THANK YOU!!

and here's my code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
int map[32][32][32];      /* wall=9  walked=9  space=0  target=100  start=1*/
int L,R,C,si,sj,sk,check;
int qui[30000],quj[30000],quk[30000],now,end;
int time[30000];
int main(void)
{
int i,j,k;
char ch;

while(scanf("%d %d %d",&L,&R,&C)&&L)
{
for(i=0;i<=31;i++)
for(j=0;j<=31;j++)
for(k=0;k<=31;k++)
{
map[i][j][k]=9;
if(i>=1&&i<=L)
if(j>=1&&j<=R)
if(k>=1&&k<=C)
{
scanf(" %c",&ch);
if(ch=='#') ;
else if(ch=='.')   map[i][j][k]=0;
else if(ch=='S') { map[i][j][k]=0; si=i; sj=j; sk=k; }
else if(ch=='E') { map[i][j][k]=100;}
}
}
/* up => setup.  down => working! */
now=0;
qui[now]=si;  quj[now]=sj;  quk[now]=sk;
time[now]=0;
end=1;
for(;now<end;now++)
{
if(map[qui[now]][quj[now]][quk[now]]==100)
{
printf("Escaped in %d minute(s).\n",time[now]);
break;
}
map[qui[now]][quj[now]][quk[now]]=9;
if( qui[now]-1>=1 && map[qui[now]-1][quj[now]][quk[now]]!=9 )
{ qui[end]=qui[now]-1; quj[end]=quj[now]; quk[end]=quk[now]; time[end]=time[now]+1; end++;}
if( quj[now]-1>=1 && map[qui[now]][quj[now]-1][quk[now]]!=9 )
{ quj[end]=quj[now]-1; qui[end]=qui[now]; quk[end]=quk[now]; time[end]=time[now]+1; end++;}
if( quk[now]-1>=1 && map[qui[now]][quj[now]][quk[now]-1]!=9 )
{ quk[end]=quk[now]-1; qui[end]=qui[now]; quj[end]=quj[now]; time[end]=time[now]+1; end++;}
if( qui[now]+1<=L && map[qui[now]+1][quj[now]][quk[now]]!=9 )
{ qui[end]=qui[now]+1; quj[end]=quj[now]; quk[end]=quk[now]; time[end]=time[now]+1; end++;}
if( quj[now]+1<=R && map[qui[now]][quj[now]+1][quk[now]]!=9 )
{ quj[end]=quj[now]+1; qui[end]=qui[now]; quk[end]=quk[now]; time[end]=time[now]+1; end++;}
if( quk[now]+1<=C && map[qui[now]][quj[now]][quk[now]+1]!=9 )
{ quk[end]=quk[now]+1; qui[end]=qui[now]; quj[end]=quj[now]; time[end]=time[now]+1; end++;}
}
if(now==end)
printf("Trapped!\n");
}
return 0;
}
``````
thanks again.

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

### Re: 532 WA ('ve tried some in/output...T^T)

I don't understand your algorithm. It looks something like floodfill , but you can't use floodfill here because you're looking for shortest time not just for connected components so you should use Breadth First Search . Could you explain your algorithm please ?

smilejfu
New poster
Posts: 5
Joined: Fri Oct 08, 2004 2:29 pm
Contact:
I used BFS to solve this problem.
but...I don't know how to explain it. (my English is not quite good ^^|||)
so...how can I do to explain my thought for you?
hmm.....|||

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

### 532

Hi, I used BFS but i was getting WA when I used a smaller array q[100000] and map[40][40][40] , then I make it queue[200000] and and map[60][60][60], and got RTE (SIGSEGV). I tried to find the error , but I could not get it. plz help me.... i keep increasing the size of array but it didn't help.

Code: Select all

`````` Accepted Now!!!!
}``````
Last edited by CodeMaker on Sun Apr 03, 2005 6:54 pm, edited 1 time in total.
Jalal : AIUB SPARKS

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
using a circular queue may help.
if u can think of it .. u can do it in software.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Yes, but isn't the queue long enough to hold all the stats? i wanted to make the code simple, they told inputs values will be <=30 , 30^3=27000, as i will never visit 1 state twice the queue should be large enough.
Jalal : AIUB SPARKS

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Hi, I have solved it now, my assumption for the size of the queue was right but the mistake was in my code, i found that i m not marking all the visited cells. only a few of them and redundancy was huge, at a result memory overflow. anyway....thanks for the reply.
Jalal : AIUB SPARKS

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### WA

Hi,
My code passes the test cases given above. I'm using DFS with memoization. Why does it not work? Can anyone give more test cases?

Here's the code:

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
#define inf 1000000000
using namespace std;

int calc(vector<vector<vector<char> > > &  maze,vector<vector<vector<int> > >  & mem,int i,int j,int k,int i1,int j1,int k1,int n_steps)
{
//cout<<i<<" "<<j<<" "<<k<<endl;
//getchar();
if(i==i1 && j==j1 && k==k1)
{
return 0;

}
else if(mem[i][j][k]!=-1)
return mem[i][j][k];
else
{
vector<int> array(6,inf);
if(i>0&& maze[i-1][j][k]!='#')
{
maze[i-1][j][k]='#';
array[0]=calc(maze,mem,i-1,j,k,i1,j1,k1,n_steps+1);
maze[i-1][j][k]='.';
}
if(i<maze.size()-1 && maze[i+1][j][k]!='#')
{

maze[i+1][j][k]='#';
array[1]=calc(maze,mem,i+1,j,k,i1,j1,k1,n_steps+1);
maze[i+1][j][k]='.';
}

if(j>0 && maze[i][j-1][k]!='#')
{

maze[i][j-1][k]='#';
array[2]=calc(maze,mem,i,j-1,k,i1,j1,k1,n_steps+1);
maze[i][j-1][k]='.';
}
if(j<maze[i].size()-1 && maze[i][j+1][k]!='#')
{

maze[i][j+1][k]='#';
array[3]=calc(maze,mem,i,j+1,k,i1,j1,k1,n_steps+1);
maze[i][j+1][k]='.';
}
if(k>0 && maze[i][j][k-1]!='#')
{

maze[i][j][k-1]='#';
array[4]=calc(maze,mem,i,j,k-1,i1,j1,k1,n_steps+1);
maze[i][j][k-1]='.';
}
if(k<maze[i][j].size()-1 && maze[i][j][k+1]!='#')
{

maze[i][j][k+1]='#';
array[5]=calc(maze,mem,i,j,k+1,i1,j1,k1,n_steps+1);
maze[i][j][k+1]='.';
}
int m=*(min_element(array.begin(),array.end()));
mem[i][j][k]=m+1;
return m+1;
}

}

int main()
{

int l,r,c;
while(1)
{
cin>>l>>r>>c;
if(l==0 && r==0 && c==0 )
break;
vector<char> col(c);
vector<vector<char> > row(r,col);
vector<vector<vector<char> > > maze(l,row);
vector<int> col1(c,-1);
vector<vector<int> > row1(r,col1);
vector<vector<vector<int> > > maze1(l,row1);
int x,y,z,x1,y1,z1;
for(int i=0;i<l;i++)
{
for(int j=0;j<r;j++)
{
for(int k=0;k<c;k++)
{
cin>>maze[i][j][k];
if(maze[i][j][k]=='S')
{x=i;y=j;z=k;}

if(maze[i][j][k]=='E')
{x1=i;y1=j;z1=k;}

}
}
}
maze[x][y][z]='#';
int n=calc(maze,maze1,x,y,z,x1,y1,z1,0);
if(n<inf )
printf("Escaped in %d minute(s).\n",n);
else
printf("Trapped!\n");
}
return 0;
}
``````

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### BFS Works

Hi,
I modified my code to bfs and it worked! But could someone tell me why DFS with memoization gives WA?

a80091221
New poster
Posts: 1
Joined: Thu Nov 29, 2007 5:08 pm

Code: Select all

``````#include<iostream>
using namespace std;
char q[33][33][33];
void find (char [33][33][33],int,int,int,int [1],int);
int main( int argc, char * argv[] )
{
int x,y,z,sx,sy,sz,i,j,g,t,ans[1];
while(( cin >> z >> y >> x )!=0)
{
t=0;
for(i=0;i<=31;i++)
for(j=0;j<=31;j++)
for(g=0;g<=31;g++)
q[i][j][g]=4;
if(x==0 || y==0 || z==0)
break;
for(i=1;i<=z;i++)
for(j=1;j<=y;j++)
for(g=1;g<=x;g++)
cin >> q[g][j][i];    // S=83 E=69 #=35 .=46
for(i=1;i<=z;i++)
for(j=1;j<=y;j++)
for(g=1;g<=x;g++)
{
if(q[g][j][i]==83)      // 2=start
{
q[g][j][i]=2;
sx=g;
sy=j;
sz=i;
}
if(q[g][j][i]==69)
q[g][j][i]=3;         // 3=exit
if(q[g][j][i]==35)
q[g][j][i]=4;         //  4=can not
if(q[g][j][i]==46)
q[g][j][i]=1;          // 1=can
}
ans[0]=0;
find(q,sx,sy,sz,ans,t);
if(ans[0]!=0)
cout << "Escaped in "<< ans[0] << " minute(s)." << endl;
else
cout << "Trapped!" << endl;
}
return 0;
}
void find(char q[33][33][33],int x,int y,int z,int ans[1],int t)
{
int i,j,g;
char qq[33][33][33];
for(i=0;i<=32;i++)
for(j=0;j<=32;j++)
for(g=0;g<=32;g++)
qq[i][j][g]=q[i][j][g];
qq[x][y][z]=0;
if(qq[x+1][y][z]==3 || qq[x-1][y][z] ==3 ||
qq[x][y+1][z]==3 || qq[x][y-1][z] ==3 ||
qq[x][y][z+1]==3 || qq[x][y][z-1] ==3 )
{
if(ans[0]==0)
ans[0]=t+1;
else
if(ans[0]>t+1)
ans[0]=t+1;
}
if(qq[x+1][y][z]==1)
find(qq,x+1,y,z,ans,t+1);

if(qq[x-1][y][z]==1)
find(qq,x-1,y,z,ans,t+1);

if(qq[x][y+1][z]==1)
find(qq,x,y+1,z,ans,t+1);

if(qq[x][y-1][z]==1)
find(qq,x,y-1,z,ans,t+1);

if(qq[x][y][z+1]==1)
find(qq,x,y,z+1,ans,t+1);

if(qq[x][y][z-1]==1)
find(qq,x,y,z-1,ans,t+1);
}

``````

why I get "Runtime Error"??[/b]

algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

### Accepted in another oj, RE in UVa oj

I'm using bfs, but I wonder which part of my code which made me got Runtime Error, would someone kind to enlighten me?
I've test my solution and got accepted in another oj

Code: Select all

``````#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAX 100
#define F(i,s,e) for(i=s;i<e;i++)

struct node{
int r,c,l;
struct node *next;

char map[MAX][MAX][MAX];
int M,N,O,Ll,Lr,Lc,vis[MAX][MAX][MAX],d[MAX][MAX][MAX];

void push(int l,int i,int j){
curr=(struct node*)malloc(sizeof(struct node))    ;
curr->r=i;
curr->c=j;
curr->l=l;
{
}
else
{
tail->next=curr;
tail=curr;
}
tail->next=0;
}

void pop(void){
free(curr);
}

int isEmpty(void){
return 0;
}

void getQueue(void){
}

void doIt(int l,int x,int y,int dep){
vis[l][x][y]=1;
d[l][x][y]=dep+1;
push(l,x,y);
// printf("level: %d\n",l);
}

void bfs(int a,int b,int c){
push(a,b,c);
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
while(!isEmpty())
{
getQueue();
pop();
int dep=d[O][M][N];
if(map[O][M][N-1]!='#'&&N-1>=0&&!vis[O][M][N-1]) doIt(O,M,N-1,dep);
if(map[O][M][N+1]!='#'&&N+1<Lc&&!vis[O][M][N+1]) doIt(O,M,N+1,dep);
if(map[O][M-1][N]!='#'&&M-1>=0&&!vis[O][M-1][N]) doIt(O,M-1,N,dep);
if(map[O][M+1][N]!='#'&&M+1<Lr&&!vis[O][M+1][N]) doIt(O,M+1,N,dep);
//lower level
if(map[O-1][M][N]!='#'&&O-1>=0&&!vis[O-1][M][N]) doIt(O-1,M,N,dep);
//upper level level
if(map[O+1][M][N]!='#'&&O+1<Ll&&!vis[O+1][M][N]) doIt(O+1,M,N,dep);

}
}

int main(){
int r,c;
int i,j,k,x,y,z,El,Ex,Ey;
char line[100];
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d %d %d\n",&Ll,&Lr,&Lc)==3)
{
if(!Ll&&!Lr&&!Lc) break;
F(i,0,Ll)
{
F(j,0,Lr) gets(map[i][j]);
gets(line);
}
F(i,0,Ll) F(j,0,Lr) F(k,0,Lc)
if(map[i][j][k]=='S') {x=i;y=j;z=k;}
else if(map[i][j][k]=='E'){El=i;Ex=j;Ey=k;}
bfs(x,y,z);
if(d[El][Ex][Ey]) printf("Escaped in %d minute(s).\n",d[El][Ex][Ey]);
else printf("Trapped!\n");
}
return 0;
}

``````

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA

### Re: 532

Hi, I hope is not too late

Look at this line: if(map[O-1][M][N]!='#'&&O-1>=0&&!vis[O-1][M][N]) doIt(O-1,M,N,dep);
The thing is that you are evaluating map[O-1][M][N] before knowing whether O-1>=0 or not, that's why you get runtime error, just switch the conditions