10377 - Maze Traversal

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

Moderator: Board moderators

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Thu Feb 05, 2004 7:50 am

so if i use cin befor gets(),the problem will accured,and scanf("%d %d",&a,&b) too
but if i use scanft("%d %d\n",&a,&b),then the problem will be ok.but a new problem will accured.if i use judge sentence like "if(a>b)",the judge will not effect until the gets() after the judge get a number
It's so weird
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

10377~~With always W.A...

Post by Wei » Wed Oct 20, 2004 1:26 pm

I alwas got W.A
Well~I don't know where is wrong??
Can anybody help me???

Code: Select all

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

int main(void)
{
  int a,m,n,i,j,k,maze[63][63]={0},d;
  char b[0];
  scanf("%d",&a);
  for(i=1;i<=a;i++)
  {
      d=1;
      scanf("%d %d",&m,&n);
      scanf("%c",&b);
      for(j=1;j<=m;j++)
      {
          for(k=1;k<=n;k++)
          {
              scanf("%c",&b);
              if(b[0]==42)
                  maze[j][k]=1;
              if(b[0]==32)
                  maze[j][k]=0;
          }
          scanf("%c",&b);
      }
      scanf("%d %d",&n,&m);
      scanf("%c",&b);
      while(b[0]!=81)
      {
          if(b[0]==82)
              d=(1+d)%4;
          if(b[0]==76)
              d=(3+d)%4;
          if(b[0]==70)
          {
              switch (d%4)
              {
                  case 1:
                      if(maze[n-1][m]==0)
                      {n--;}
                      break;
                  case 2:
                      if(maze[n][m+1]==0)
                      {m++;}
                      break;
                  case 3:
                      if(maze[n+1][m]==0)
                      {n++;} 
                      break;
                  case 0:
                      if(maze[n][m-1]==0)
                      {m--;}
                      break;
              }
          }
          scanf("%c",&b);
      }
      printf("%d %d",n,m);
      switch (d%4)
      {
          case 1:
              printf(" N\n\n");
              break;
          case 2:
              printf(" E\n\n");
              break;
          case 3:
              printf(" S\n\n"); 
              break;
          case 0:
              printf(" W\n\n");
              break;
      }
  }
  return 0;
}

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

Post by Wei » Sun Oct 24, 2004 4:47 am

Well~forget about the last message I post...
Now...I got an AC~~

haik111
New poster
Posts: 1
Joined: Tue Feb 01, 2005 3:47 pm

plz help me

Post by haik111 » Tue Feb 01, 2005 7:25 pm

my program got WA plz help me
// acm 10377

Code: Select all

#include <iostream>
using namespace std;

struct rob
{
	int x;
	int y;
	int f;
};
const int NMAX = 1000;
const char orent[] = "NESW";
char a[NMAX][NMAX];
char temp[NMAX];
int ROW, COLUMN;
rob robot;

main()
{
	int q, i;
	char c;
	cin >> q;

	while (q-- != 0)
	{
		cin >> ROW >> COLUMN;
		cin.getline(temp, NMAX);

		for (i = 0; i < ROW; i++)
			cin.getline(a[i], NMAX);

		cin >> robot.x >> robot.y;
		robot.f = 0;
		robot.x--;
		robot.y--;
	
		cin.get(c);
		while (c != 'Q')
		{
			if (c == 'R')
				robot.f = (robot.f + 1) % 4;
			if (c == 'L')
				robot.f = (robot.f == 0) ? 4 : robot.f - 1;
			if (c == 'F')
			{
				if (robot.f == 0 && a[robot.x - 1][robot.y] == ' ')
					robot.x--;
				if (robot.f == 1 && a[robot.x][robot.y + 1] == ' ')
					robot.y++;
				if (robot.f == 2 && a[robot.x + 1][robot.y] == ' ')
					robot.x++;
				if (robot.f == 3 && a[robot.x][robot.y - 1] == ' ')
					robot.y--;

			}
			cin.get(c);
		}
		cout << ++robot.x << " " << ++robot.y << " " << orent[robot.f] << '\n';
		if (q != 0)
			cout << '\n';
	
	}

	return 0;
}
----------

SRXz
New poster
Posts: 2
Joined: Sat May 14, 2005 8:15 am

10377 WA

Post by SRXz » Sat May 14, 2005 8:18 am

Code: Select all


special input??


#include <iostream>
#include <cstdio>
#include <string>

using namespace std ;
char C[4]={'N','E','S','W'} ;

int go(char map[100][100],int &x,int &y,int now){
 
  if(C[now%4]=='N')
              if(map[x-1][y]==' ')
                                  x--;
           
  if(C[now%4]=='E')
              if(map[x][y+1]==' ')
                                  y++;
  if(C[now%4]=='S')
              if(map[x+1][y]==' ')
                                  x++;
  
  if(C[now%4]=='W')
              if(map[x][y-1]==' ')
                                  y--;
}
int main(){
int times,i ,x ,y , j ,nx=0,ny=0;
char input[500],a ;
 cin >> times ;   
 cout << endl ;
 
 while (times>0){
   int out=0,now=0 ;
   cin >> x >> y ;
   char map[100][100]={0} ;
       getchar();
       for(i=0;i<x;i++)
                  gets(map[i]);
     
    cin >> nx >> ny ; 
     while( out==0 && gets(input)   ){ 
        for(i=0;i<strlen(input);i++){
      
                     switch(input[i]){
                     
                     case 'F' :
                               go(map,nx,ny,now) ; 
                               break ; 
                     case 'L' :
                               now-- ;
                               break ; 
                     case 'R' :
                               now++ ;
                               break ;
                     case 'Q' : 
                                out=1 ;
                                break ;
                    
                   }    
      }  
  }  
   cout << nx+1 << " " << ny+1 << " " <<C[now%4] << endl << endl ; 
   times-- ;
  }     
}    
I don't know why always WA

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Sat May 14, 2005 10:08 am

I haven't tested your code, but you should be aware that (-1)%4=(-1) and not 3 as you would want to in this case.

SRXz
New poster
Posts: 2
Joined: Sat May 14, 2005 8:15 am

Post by SRXz » Sat May 14, 2005 12:59 pm

dumb dan wrote:I haven't tested your code, but you should be aware that (-1)%4=(-1) and not 3 as you would want to in this case.
thanks , ans I got AC(P.E)

(and nx-- ny-- I should add in my code )

User avatar
Jordi Aranda
New poster
Posts: 13
Joined: Wed Apr 29, 2009 11:37 am
Location: Barcelona

Re: 10377 - Maze Traversal

Post by Jordi Aranda » Tue Mar 23, 2010 3:09 pm

I think I'm not understanding this problem in a right way. Take into account the input, my final position doesn't match with the output:

Code: Select all

Removed after accepted
Born to be wild

mostafakhattab
New poster
Posts: 1
Joined: Tue Aug 16, 2011 6:02 pm

Re: 10377 - Maze Traversal

Post by mostafakhattab » Tue Aug 16, 2011 6:10 pm

I got WA,

Code: Select all

#include <iostream>
using namespace std;

int main() {
	int n = 0, row = 0, col = 0, sR = 0, sC = 0;
	char direct = 'N', c;
	cin >> n;
	while (1) {
		if (n == 0)
			break;
		n--;
		cin >> row >> col;
		char maze[row][col];
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				cin >> maze[i][j];
			}
		}
		cin >> sR >> sC;
		sR -= 1;
		sC -= 1;
		while (cin >> c) {
			if (c == 'Q'){
			cout << sR << " " << sC << " " << direct << endl;
			}
			else if (c == 'R') {
				if (direct == 'N')
					direct = 'E';
				else if (direct == 'E')
					direct = 'S';
				else if (direct == 'S')
					direct = 'W';
				else if (direct == 'W')
					direct = 'N';
			} else if (c == 'L') {
				if (direct == 'N')
					direct = 'W';
				else if (direct == 'W')
					direct = 'S';
				else if (direct == 'S')
					direct = 'E';
				else if (direct == 'E')
					direct = 'N';
			} else if (c == 'F') {
				if (direct == 'E') {
					if (maze[sR][sC + 1] != '*' && sC + 1 < col) {
						sC += 1;
					}
				} else if (direct == 'S') {
					if (maze[sR + 1][sC] != '*' && sR + 1 < row) {
						sR += 1;
					}

				} else if (direct == 'W') {
					if (maze[sR][sC - 1] != '*' && sC - 1 >= 0) {
						sC -= 1;
					}

				} else if (direct == 'N') {
					if (maze[sR - 1][sC] != '*' && sR - 1 >= 0) {
						sR -= 1;
					}
				}
			}
		}
	}
	return 0;
}

sabbir_alam_ufo
New poster
Posts: 16
Joined: Fri Nov 15, 2013 9:33 pm

Re: 10377 - Maze Traversal

Post by sabbir_alam_ufo » Wed Jan 28, 2015 8:33 am

Getting WA please help !!!

Code: Select all

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cctype>
#include<set>
#include<bitset>
#include<algorithm>
#include<list>

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>

using namespace std;
#define print1(a)    cout<<a<<endl
#define print2(a,b) cout<<a<<" "<<b<<endl
#define print3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define oo          (1<<30)
#define PI          3.141592653589793
#define pi          (2.0*acos(0.0))
#define ERR         1e-5
#define PRE         1e-8
#define SZ(s)       ((int)s.size())
#define LL          long long
#define ISS         istringstream
#define OSS         ostringstream
#define VS          vector<string>
#define VI          vector<int>
#define VD          vector<double>
#define VLL         vector<long long>
#define SII         set<int>::iterator
#define SI          set<int>
#define mem(a,b)    memset(a,b,sizeof(a))
#define fr(i,a,b)   for(i=a;i<=b;i++)
#define frn(i,a,b)  for(i=a;i>=b;i--)
#define fri(a,b)    for(i=a;i<=b;i++)
#define frin(a,b)   for(i=a;i>=b;i--)
#define frj(a,b)    for(j=a;j<=b;j++)
#define frjn(a,b)   for(j=a;j>=b;j--)
#define frk(a,b)    for(k=a;k<=b;k++)
#define frkn(a,b)   for(k=a;k>=b;k--)
#define frl(a,b)    for(l=a;l<=b;l++)
#define frln(a,b)   for(l=a;l>=b;l--)
#define REP(i,n)    for(i=0;i<n;i++)
#define EQ(a,b)     (fabs(a-b)<ERR)
#define all(a,b,c)  for(int I=0;I<b;I++)    a[I] = c
#define CROSS(a,b,c,d) ((b.x-a.x)*(d.y-c.y)-(d.x-c.x)*(b.y-a.y))
#define sqr(a)      ((a)*(a))
#define FORE(i,a)   for(typeof((a).begin())i=(a).begin();i!=(a).end();i++)
#define typing(j,b) typeof((b).begin()) j=(b).begin();
#define BE(a)       a.begin(),a.end()
#define rev(a)      reverse(BE(a));
#define sorta(a)    sort(BE(a))
#define pb          push_back
#define popb        pop_back
#define mp          make_pair
#define round(i,a)  i = ( a < 0 ) ? a - 0.5 : a + 0.5;
#define makeint(n,s)  istringstream(s)>>n
#define inpow(a,x,y) int i; a=x;fri(2,y)  a*=x
#define cntbit(mask) __builtin_popcountll(mask)
//0 based print
#define debug_array(a,n) for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;
#define debug_matrix(mat,row,col) for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}

#define csprnt printf("Case %d: ", ++cas);
#define mod         1000000007
#define eulerconstant 0.5772156649

template<class T1> void debug(T1 e){cout<<e<<endl;}
template<class T1,class T2> void debug(T1 e1,T2 e2){cout<<e1<<"\t"<<e2<<endl;}
template<class T1,class T2,class T3> void debug(T1 e1,T2 e2,T3 e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
template<class T1,class T2,class T3,class T4> void debug(T1 e1,T2 e2,T3 e3,T4 e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
template<class T1,class T2,class T3,class T4,class T5> void debug(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
template<class T1,class T2,class T3,class T4,class T5,class T6> void debug(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<"\t"<<e6<<endl;}
template<class T> void debug(vector< vector<T> > e,int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;} cout<<endl;}
template<class T> void debug(vector< basic_string<T> > e,int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j];cout<<endl;} cout<<endl;}
template<class T> void debug(T e[110][110],int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
bool isVowel(char ch){ch=tolower(ch);if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}
bool isUpper(char c){return c>='A' && c<='Z';}
bool isLower(char c){return c>='a' && c<='z';}
/***************************************************code starts from here*************************************************************************************************/

int cRow,cCol,face;
int row,col;
char maze[100][100],ch;
char convert(int f)
{
    if(f==1)
        return 'N';
    else if(f==-1)
        return 'S';
    else if(f==-2)
        return 'W';
    else if(f==2)
        return 'E';
}
bool valid(int r,int c)
{
    if(r<0)
        return false;
    else if(r>=row)
        return false;
    else if(c<0)
        return false;
    else if(c>=col)
        return false;
    return true;
}
void movement(char c,int cr,int cc,int f)
{
    if(c=='F')
    {
        if(f==1)
        {
            if(maze[cr-1][cc]!='*' && valid(cr-1,cc))
            {
                cr--;
            }
        }
        else if(f==-1)
        {
            if(maze[cr+1][cc]!='*'&&valid(cr+1,cc))
            {
                cr++;
            }
        }
        else if(f==2)
        {
            if(maze[cr][cc+1]!='*'&&valid(cr,cc+1))
            {
                cc++;
            }
        }
        else if(f==-2)
        {
            if(maze[cr][cc-1]!='*'&&valid(cr,cc-1))
            {
                cc--;
            }
        }
    }
    else if(c=='R')
    {
        switch(f)
        {
            case 1: f=2;break;
            case 2: f=-1;break;
            case -1: f=-2;break;
            case -2: f=1;break;
            default:break;
        }
    }
    else if(c=='L')
    {
        switch(f)
        {
            case 1: f=-2;break;
            case -2: f=-1;break;
            case -1: f=2;break;
            case 2: f=1;break;
            default: break;
        }
    }
    cRow=cr;
    cCol=cc;
    face=f;
    return ;
}

int main()
{
    int tCase,nCase;
    cin>>tCase;
    fr(nCase,1,tCase)
    {
         cout<<endl;

        face=1;//north=1, south=-1,west=-2,east=2
        cin>>row>>col;
        mem(maze,0);
        int i,j;
        getchar();
        fr(i,0,row-1)
        {
            gets(maze[i]);
            //cout<<maze[i]<<endl;
            //getchar();
        }
        /*fr(i,0,row-1)
        {
            fr(j,0,col-1)
            {
                cout<<maze[i][j];
            }
            cout<<endl;
        }*/

        cin>>cRow>>cCol;
        cin>>ch;
        cRow--;
        cCol--;
        //cout<<ch<<endl;
        i=0;
        while(ch!='Q')
        {
            i++;
            movement(ch,cRow,cCol,face);
            cin>>ch;
            //cout<<i<<" "<<ch<<" "<<cRow<<" "<<cCol<<" "<<convert(face)<<endl;
        }

        cout<<cRow+1<<" "<<cCol+1<<" "<<convert(face)<<endl;
        cout<<endl;
    }
    return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10377 - Maze Traversal

Post by brianfry713 » Wed Jan 28, 2015 10:47 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10377 - Maze Traversal

Post by uDebug » Fri Mar 27, 2015 1:49 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 103 (10300-10399)”