10377 - Maze Traversal

[karl]

Love&peace to everyone!


10377 is very simple, I thought.
Judge says that my programm produces TLE but I can't figure out the reason. Here's my code.

Code: Select all

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>

char maze[62][62];
int row,col, crow,ccol;
int facing;
char command;
int runs,crun;
int posrow,poscol;
char line[62];
bool first=true;


void init_maze()
{
 int c,r;
 for(c=0;c<62;c++)
 for(r=0;r<62;r++)
    maze[c][r]='*';
}


int main()
{

    cin >> runs;
    for(crun=0;crun<runs;crun++)
    {
      // -- actual size of maze
      cin >> row >> col;

      // -- read maze
      init_maze();
      for(crow=1;crow<row+1;crow++)
      {
      gets(line);
      for(ccol=1;ccol<col+1;ccol++)
        {
          maze[crow][ccol]=line[ccol-1];
          }
       }
      // -- read starting position
      cin >> posrow >> poscol;

      // -- facing; 0=N, 1=E, 2=S, 3=W!
      facing=0;

      // -- read commands and do the job :-)
      cin >> command;
      while(command!='Q')
      {
      switch(command)
      {
      case 'R'       :   if (facing==3) facing=0;
                         else facing++;
                         break;
      case 'L'       :   if (facing==0) facing=3;
                         else facing--;
                         break;
      case 'F'       :   switch(facing)
                         {
                         case 0        : if (maze[posrow-1][poscol]!='*')
                                         posrow--; break;
                         case 1        : if (maze[posrow][poscol+1]!='*')
                                         poscol++; break;
                         case 2        : if (maze[posrow+1][poscol]!='*')
                                         posrow++; break;
                         case 3        : if (maze[posrow][poscol-1]!='*')
                                         poscol--; break;
                         }
                         break;
      default         : ;
      }
      cin >> command;
      }
      // -- output and next one!
      if (first==true) first=false;
      else cout << endl;
      cout << posrow << " " << poscol << " ";
      switch(facing)
      {
      case 0        : cout << "N"; break;
      case 1        : cout << "E"; break;
      case 2        : cout << "S"; break;
      case 3        : cout << "W"; break;
      }
      cout << endl;
     }
      return 0;
}

Hope you have some hints for me, what's going wrong.
I guess, it's something with reading input, but what exactly???

Karl

[EZE]

Without actually compiling and running your program, I can only guess as to what the possible problems are. First is that each set of inputs is separated by a blank line... did you account for that? Second, the maze may have an exit... I dont think this is your problem, but you dont account for that. Third.... NEVER use gets - it's evil .... use cin.getline instead... it has bounds checking. Try changing those things and see what happens Hope this helps!

ciao
EZE

[supermin]

I got P.E. Accepted,but I still can't find the wrong with the P.E. problem..
Could somebody excute my source code and find my wrong..thanks!!

ps.I think this blank lines are troubles...........

Code: Select all

#include<stdio.h>
#define MAX 61
#define E 1
#define W 2
#define S 3
#define N 4

int chan_dir(int ,char);

int main(void)
{
 int row,column;
 int maze[MAX][MAX];
 char c;
 int i,j;
 int s_r,s_c;
 int direction;

 int times;

 scanf("%d",&times);
 printf("\n");
 while(times-->0)
 {
	 scanf("%d %d",&row,&column);
  
	 for(i=1;i<=row;i++)
		 for(j=1;j<=column;)
		 {
			 scanf("%c",&c);
			 if(c=='*') maze[i][j]=1;
			 else if(c==' ') maze[i][j]=0;
			 else continue;
	         j++;
		 }

	 scanf("%d %d",&s_r,&s_c);
	 direction=N;

	while((c=getchar())!=EOF)
	{
		if(c!='R'&&c!='L'&&c!='F'&&c!='Q') continue;

		if(c=='R'||c=='L') direction=chan_dir(direction,c);
		else if(c=='F')/* mean move forward */
		{
			if(direction==N&&maze[s_r-1][s_c]!=1) s_r--;
			else if(direction==S&&maze[s_r+1][s_c]!=1) s_r++;
			else if(direction==E&&maze[s_r][s_c+1]!=1) s_c++;
			else if(direction==W&&maze[s_r][s_c-1]!=1) s_c--;
		}
		else break;
	}

	if(direction==E) c='E';
	else if(direction==W) c='W';
	else if(direction==S) c='S';
	else c='N';

	printf("%d %d %c",s_r,s_c,c);
	if(times) printf("\n\n");
 }
 return 0;
}

int chan_dir(int old,char turn)
{
 if(turn=='R')
 {
  if(old==N) return E;
  else if(old==S) return W;
  else if(old==E) return S;
  else return N;
 }
 else
 {
  if(old==N) return W;
  else if(old==S) return E;
  else if(old==E) return N;
  else return S;
 }
}

[rakeb]

I got P.E. Accepted,but I still can't find the wrong with the P.E. problem..
Could somebody excute my source code and find my wrong..thanks!!

ps.I think this blank lines are troubles...........

Code: Select all

 scanf("%d",&times);
 printf("\n");
 while(times-->0)
 {
	----------------------------------
                ----------------------------------
	printf("%d %d %c",s_r,s_c,c);
	if(times) printf("\n\n");
 }
 return 0;
}

u r printing an extra blak line before entering the loop but problem says

The outputs of two consecutive cases will be separated by a blank line

just do like this

Code: Select all

scanf("%d",&times); 
sp=0;
while(times-->0) 
{ 
  --------------------------
  ---------------------------- 
   if(sp)printf("\n");sp=1;
   printf("%d %d %c\n",s_r,s_c,c); 
} 

[supermin]

Thank you!!
I got accepted.

[alexkro]

My program works correctly on sample input, but it gets "wrong output" if I submit it. what could be wrong? Are there any special cases not described clearly?

[justforfun]

are there any special input for this problem?
cause i got WA but can't find out why
can anybody help me~~

Code: Select all

#include<stdio.h>
#include<string.h>
int arr[61][61];
int main(void)
{
    int count,nl=0;
    char cmd;
    scanf("%d",&count);
    while (count)
    {
	int row,col,i,j,x,y,direct=0,dir;
        scanf("%d %d",&row,&col);
        getchar();
	for (i=0;i<row;i++)
	    gets(arr[i]);	    
	scanf("%d %d",&x,&y);

	while ((cmd=getchar())!='Q')
	{	    	   	    
	    if (cmd=='R')
	        direct++;
	    else if (cmd=='L')
		direct--;
	    else if (cmd=='F')
            {
		dir=direct%4;
		if (dir==0 && x-2>=0 && arr[x-2][y-1]!='*')
		    x--;
		else if (dir==2 && x<row && arr[x][y-1]!='*')		    
	   	    x++;			
		else if (dir==1 && y<col && arr[x-1][y]!='*')		    
		    y++;			
		else if (y-2>=0 && arr[x-1][y-2]!='*')
	 	    y--;
	    }	    
	}
	if (nl)
	    printf("\n");
	nl=1;
	printf("%d %d ",x,y);
	dir=direct%4;
	if (dir==0)
	    printf("N\n");
	else if (dir==1)
	    printf("E\n");
	else if (dir==2)
	    printf("S\n");
	else
	    printf("W\n");
	count--;
    }
    return 0;
}

[LittleJohn]

are there any special input for this problem?
cause i got WA but can't find out why
can anybody help me~~

1) arr should be char[][], not int[][]
2) you used just only one getchar() after reading row and col,
it will be wrong if there're spaces after those two integers. I suggest you correct it.
3) C doesn't like Pascal, -1 % 4 = -1, not 3, so direct-- in your program should be modified.
Good Luck

[lendlice]

Code: Select all

//10377
#include<stdio.h>
#include<string.h>
main()
{
 int many=0,a,b,i=0,j=0,now1,now2,n,s=0,tr=0;
 char in[100][100],line[1000],state[6]="NESW";
 scanf("%d\n",&many);
 while(many>0)
 {
  scanf("%d%d%*c",&a,&b);
  for(i=0;i<a;i++)
   gets(in[i]);

  scanf("%d%d",&now1,&now2);
  s=0;
  now1--;
  now2--;
  if(now1<a&&now2<b)
  {
   while(gets(line))
   {
    n=strlen(line);
    for(i=0;i<n;i++)
    {
     if(line[i]=='R')
      s++;
     if(line[i]=='L')
      s=s+3;
     if(line[i]=='Q')
      tr=1;
     if(line[i]=='F')
     {
      s=s%4;
      if(s==0)
      {
       if((now1-1)>=0)
        if(in[now1-1][now2]!='*')
         now1--;
      }
      else if(s==1)
      {
       if((now2+1)<b)
       {
        if(in[now1][now2+1]!='*')
           now2++;
       }
      }
      else if(s==2)
      {
       if((now1+1)<a)
       if(in[now1+1][now2]!='*')
         now1++;
      }
      else if(s==3)
      {
       if((now2-1)>=0)
        if(in[now1][now2-1]!='*')
          now2--;
      }
     }
    }
    if(tr==1)
     break;
   }
   printf("%d %d %c\n",now1+1,now2+1,state[s]);
   many--;
   tr=0;
  }
 }
}

Anyone can tell me.
what's wrong with my code.
thanks

[miras]

Ello i have just got AC(P.E)



but did U tried with s. inoput:
1

4 4
****
* **
* **
****
2 2
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFF FFFFQ





the output


2 2 N
_________________________________
MTFBWY


MiRas

[miras]

remember


INPUT

3 3
***
* *
***
2 2
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFF1 Q

OUPUT

2 2 N


________________________________
MTFBWY



MiRas

[boatfish]

I have considered all the possibilities that I can think about, but still WA.

Code: Select all

#include<iostream>
using namespace std;

char table[61][61];
enum oreo{N,E,S,W};

int main(){
	int case_no,r,c,i,j,x,y;
	char bu;
	oreo ori;
	cin>>case_no;
	while(case_no--){
		cin>>r>>c;
		cin.get(bu);
		for(i=1;i<=r;i++){
			for(j=1;j<=c;j++){
				cin.get(bu);
				table[i][j]=bu;
			}
			cin.get(bu);
		}
		cin>>x>>y;
		ori=N;
		while(cin>>bu){
			if(bu=='Q'){
				cout<<x<<' '<<y<<' ';
				switch(ori){
					case N:
						cout<<'N';
						break;
					case E:
						cout<<'E';
						break;
					case S:
						cout<<'S';
						break;
					default:
						cout<<'W';
				}
				cout<<endl;
				break;
			}
			else if(bu=='R')
				ori=oreo((ori+1)%4);
			else if(bu=='L')
				ori=oreo((ori-1)%4);
			else
				if(ori==N)
					if(x-1>=1 && table[x-1][y]!='*')
						x--;
					else;
				else if(ori==E)
					if(y+1<=c && table[x][y+1]!='*')
						y++;
					else;
				else if(ori==S)
					if(x+1<=r && table[x+1][y]!='*')
						x++;
					else;
				else
					if(y-1>=1 && table[x][y-1]!='*')
						y--;
		}
		if(case_no)
			cout<<endl;
	}
	return 0;
}

[gawry]

Code: Select all

ori=oreo((ori-1)%4);

You must change it into:

Code: Select all

ori=oreo((3+ori)%4);

because in C x%y is not always positive (you get negative result when x<0 and y>0)

Code: Select all

if(ori==N) 
  if(x-1>=1 && table[x-1][y]!='*')
    x--;
  else;
else if(ori==E)
  if(y+1<=c && table[x][y+1]!='*')
    y++;
  else;
else if(ori==S)
  if(x+1<=r && table[x+1][y]!='*')
    x++;
  else;
else
  if(y-1>=1 && table[x][y-1]!='*')
    y--;

Delete first parts of those conditions (x-1>=1,y+1<=c,...)

[boatfish]

Thx very much!
I got AC.

[Morning]

when i try to solve 10377,the gets() puzzled me a lot

Code: Select all

#include "iostream.h" 
#include "string.h"
#include "stdio.h" 

int main(int argc, char* argv[]) 
{ 
   char maze[61][61],operation[1000],ori; 
   int numOfCase,row,column,temp,initX,initY,x,y,orient,flag; 
   cin>>numOfCase; 
   while(numOfCase>0) 
   { 
      orient=0; 
      numOfCase--; 
      cin>>row>>column;
      //problem here,after i entered the value of row and column
      //the gets() below will read the later automatically
      //how can i solve this problem?
      for(temp=0;temp<row;temp++) 
	  {
		  gets(maze[temp]); //This gets()!!!
		  cout<<"maze["<<temp<<"]"<<endl;
	  }
      cin>>initX>>initY; 
      x=initX; 
      y=initY; 
      while(1) 
      { 
         flag=0; 
         cin>>operation; 
         for(temp=0;temp<(int)strlen(operation);temp++) 
         { 
            switch(operation[temp]) 
            { 
            case 'L': 
               orient--; 
               if (orient<0) orient=3; 
               break; 
            case 'R': 
               orient++; 
               if (orient>3) orient=0; 
               break; 
            case 'F': 
               switch(orient) 
               { 
               case 0: 
                  if(maze[x-2][y-1]!='*') x--; 
                  break; 
               case 1: 
                  if(maze[x-1][y]!='*') y++; 
                  break; 
               case 2: 
                  if(maze[x][y-1]!='*') x++; 
                  break; 
               case 3: 
                  if(maze[x-1][y-2]!='*') y--; 
                  break; 
               } 
               break; 
            case 'Q': 
               flag=1; 
               break; 

            } 
            if(flag==1) break; 

         } 
         if(flag==1) break; 
      } 
      switch(orient) 
      { 
      case 0: 
         ori='N'; 
         break; 
      case 1: 
         ori='E'; 
         break; 
      case 2: 
         ori='S'; 
         break; 
      case 3: 
         ori='W'; 
         break; 
      } 
      cout<<x<<" "<<y<<" "<<ori<<endl; 
       
   } 
   return 0; 
}