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

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

532 WA!!!

Post by lky » Wed Feb 18, 2004 4:48 pm

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;
var i,j,k,x,y,z,head,tail,sx,sy,sz,fx,fy,fz:longint;
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;
head:=head+1;
bfs(head)
end;
begin
readln(x,y,z);
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
then readln
until not eoln;
for i:=1 to x do
begin
for j:=1 to y do
begin
for k:=1 to z do
read(a[i,j,k]);
readln
end;
readln
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;
head:=1;
tail:=1;
b[sx,sy,sz]:=true;
qx[head]:=sx;
qy[head]:=sy;
qz[head]:=sz;
len[head]:=0;
bfs(head);
readln(x,y,z)
end
end.

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

Post by lky » Thu Feb 19, 2004 5:35 pm

i finally solved this....this is simply some problem in the operation with the b varibales

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Post by Ming Han » Sun Nov 28, 2004 3:34 pm

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)

Post by smilejfu » Fri Jan 21, 2005 6:29 pm

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. :D

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

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

Post by nnahas » Tue Jan 25, 2005 12:48 am

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:

Post by smilejfu » Mon Jan 31, 2005 10:07 am

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.....|||

(still thanks for your reply :D )

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

532

Post by CodeMaker » Sun Apr 03, 2005 2:52 pm

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

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Sun Apr 03, 2005 4:25 pm

using a circular queue may help.
if u can think of it .. u can do it in software.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sun Apr 03, 2005 4:38 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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sun Apr 03, 2005 6:53 pm

Hi, :D 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

Post by ranban282 » Fri Aug 18, 2006 8:53 pm

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

Post by ranban282 » Sat Aug 19, 2006 5:32 am

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

Please help me !

Post by a80091221 » Thu Nov 29, 2007 5:17 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);
}

Please help me!

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

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

Accepted in another oj, RE in UVa oj

Post by algoJo » Thu Mar 06, 2008 9:14 pm

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;
}*head,*curr,*tail;

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;
    if(!head)
    {
        head=tail=curr;
    }  
    else
    {
        tail->next=curr;
        tail=curr;
    }      
    tail->next=0;
}

void pop(void){
    curr=head;
    head=curr->next; 
    free(curr);  
}

int isEmpty(void){
    if(!head) return 1;
    return 0;    
}

void getQueue(void){
    O=head->l;
    M=head->r;
    N=head->c;    
}

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

Post by ExUCI » Wed Jan 07, 2009 3:04 am

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 :D

Remove your code after AC
Remove your code after AC :)

Post Reply

Return to “Volume 5 (500-599)”