118 - Mutant Flatworld Explorers

[Neo]

Subeen:
I don't think that there is any special or critical input ( I got Accepted). I need to know what kind of problem you are facing. This
seems to be a straight forward problem.

------------------------------------------------------------
Try this. If you still have problem write again.
Good Luck.
Neo

[przygoda]

[pascal]
Please help .
I have got WA .
Here is my code

program ogrod;

var
i,ilosc,pom,poz,x1,y1,x,y:longint;
z:char;
lost:boolean;
t:array[1..200,1..3] of byte;

begin
readln(x,y);
while not eof do begin
readln(x1,y1,z,z);
case z of
'N' : poz:=1;
'E' : poz:=2;
'S' : poz:=3;
'W' : poz:=4;
end;
lost:=false;

while not eoln do begin
if (x1 > x ) or (y1 > y) or (x1<0) or (y1<0) then begin
lost:=true;
inc(ilosc);
t[ilosc,1]:=x1;
t[ilosc,2]:=y1;
t[ilosc,3]:=poz;
end;

read(z);
case z of
'F' : pom:=0;
'L' : pom:=1;
'R' : pom:=2;
end;

if pom = 0 then begin

if poz=1 then begin
inc(y1);
for i:=1 to ilosc do

if (t[i,1]=x1) and (t[i,2]=y1) and (t[i,3]=poz) then begin
dec(y1);
break;
end;

continue;
end;

if poz=2 then begin
inc(x1);
for i:=1 to ilosc do

if (t[i,1]=x1) and (t[i,2]=y1) and (t[i,3]=poz) then begin
dec(x1);
break;
end;

continue;
end;

if poz=3 then begin
dec(y1);
for i:=1 to ilosc do

if (t[i,1]=x1) and (t[i,2]=y1) and (t[i,3]=poz) then begin
inc(y1);
break;
end;

continue;
end;

if poz=4 then begin
dec(x1);
for i:=1 to ilosc do

if (t[i,1]=x1) and (t[i,2]=y1) and (t[i,3]=poz) then begin
inc(x1);
break;
end;

continue;
end;
end;

if pom = 1 then begin
dec(poz);
if poz=0 then poz:=4;
end;

if pom = 2 then begin
inc(poz);
if poz=5 then poz:=1;
end;

end;

write(x1,' ',y1,' ');
case poz of
1 : write('N');
2 : write('E');
3 : write('S');
4 : write('W');
end;

if lost then
write(' ','LOST');
writeln;

readln;
end;
end.[/pascal]

[Robbie]

I think you should read this carefully :

- Left: the robot turns left 90 degrees and remains on the current grid point.

-Right: the robot turns right 90 degrees and remains on the current grid point.

-Forward: the robot moves forward one grid point in the direction of the current orientation and mantains the same orientation.

[Subeen]

my code is here:

[c]
code removed
[/c]

[Yarin]

if(tx > m || tx < 0 || ty > n || ty < 0)
{
if(!scent[tx][ty])
{
scent[tx][ty] = 1;
flag = 0;
}
else

This looks dangerous, if tx<0 or ty<0, you will write outside the array. Also, your program fails on the following data:

5 3
0 0 E
FFFFFF
0 0 E
FFFFFRF

It should return

5 0 E LOST
5 0 S

The last robot should not fall of the edge; the scent is left on the actual square, even if the robot falls out in another direction.

[Subeen]

thanks for help i got it AC

[Olorin]

Heck, I don't see what's wrong with it:
If you see something wrong, let me know, please.
Thanks in advance.

[cpp]
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// Problem 105: "Mutant Flatworld Explorers"
// Submission by Frank "Olorin" Rizzi
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

// Libraries:
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
#include <cstdlib>
#include <cmath>
#include <climits>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

// Constants and typedefs:
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
const int MAX = 100;
const int N =0;
const int E =1;
const int S =2;
const int W =3;

// Data Structures:
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
struct Bot
{
int r;
int c;
int d;
bool alive;

void Exe(char cmd, char map[MAX][MAX], int h, int w)
{
int oldr=r;
int oldc=c;
int oldd=d;

bool done=false;
switch(cmd)
{
case 'F':
switch(d)
{
case N:
if(map[r][c]!='N')
{ done=true; r--; }
break;
case S:
if(map[r][c]!='S')
{ done=true; r++; }
break;
case E:
if(map[r][c]!='E')
{ done=true; c++; }
break;
case W:
if(map[r][c]!='W')
{ done=true; c--; }
break;
default:
break;
}//SWITCH
break;
case 'R': //Turn Left:
switch(d)
{
case N: d=W; break;
case W: d=S; break;
case S: d=E; break;
case E: d=N; break;
default: break;
}//SWITCH
break;
case 'L': //Turn Right:
switch(d)
{
case N: d=E; break;
case E: d=S; break;
case S: d=W; break;
case W: d=N; break;
default: break;
}//SWITCH
break;
default:
break;
}//SWITCH

if(done)
if(r<0 || r>h || c<0 || c>w)
{
char badC='x';
switch(oldd)
{
case N: badC='N'; break;
case S: badC='S'; break;
case E: badC='E'; break;
case W: badC='W'; break;
default: break;
}//SWITCH
map[oldr][oldc]=badC;
alive=false;
r = oldr;
c = oldc;
d = oldd;
}//IF

}
//End Exe

};//End Bot struct

// Prototypes:
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void SetUp(char map[MAX][MAX], int H, int W);
void Process(char map[MAX][MAX], int H, int W,
int startR, int startC, char startDC, string cmds);



//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// main
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void main()
{
int W;
int H;

cin>>W>>H;
cin.ignore(100, '\n');

char map[MAX][MAX];
SetUp(map, H, W);

string line;
while(getline(cin, line))
{
istringstream is(line);
int startC;
int startR;
char dirc;
is>>startC>>startR>>dirc;
getline(cin, line);
Process(map, H, W, startR, startC, dirc, line);
}//WEND
}
// End main
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

// Process:
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void Process(char map[MAX][MAX], int h, int w,
int startR, int startC, char startDC, string cmds)
{
Bot b;
b.r=startR;
b.c=startC;
b.alive=true;
switch(startDC)
{
case 'N': b.d=S; break;
case 'S': b.d=N; break;
case 'E': b.d=E; break;
case 'W': b.d=W; break;
default: b.d=-1; break;
}//SWITCH
int L = cmds.size();
for(int i=0; i<L; i++)
if(b.alive) b.Exe(cmds, map, h, w);


cout<<b.c<<" "<<b.r<<" ";
switch(b.d)
{
case N: cout<<'S'; break;
case S: cout<<'N'; break;
case E: cout<<'E'; break;
case W: cout<<'W'; break;
default: cout<<'?'; break;
}//SWITCH
if(!b.alive) cout<<" LOST";
cout<<endl;
}
//End Process
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

// SetUp:
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void SetUp(char map[MAX][MAX], int H, int W)
{
for(int i=0; i<=H; i++)
for(int j=0; j<=W; j++)
map[j]='.';
}
//End SetUp
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// EOF
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[/cpp]

[JTK1996]

From the problem description I guess Your 'lost'-condition is wrong.
A robot can not "drop off the world at the same grid point",
so it should be the field that matters, not the direction.
Hope that helps.

[JTK1996]

Hi Olorin,
I got accepted now, so my feelin

[Olorin]

JTK1996,
Thanks, I will try your suggestion.
The third bot in the sample case, I believe, could work both ways... that might be what tricked me
While, getting it wrong, as apparently I did, would give the wrong answer in a croner, for instance...

Thanks again: good thinking !

[pheres]

Can anyone help me?

[pascal]
Program P118;
Type pos=record
x,y:integer;
o:char;
end;
Var lx,ly,p,dir,i:integer;
orders:string;
r:pos;
fim,scent:boolean;
field:array[1..51,1..51] of integer;

Function turn(c:char):integer;
Begin
if c='R' then inc(dir);
If c='L' then dec(dir);
if dir=5 then turn:=1
else if dir=0 then turn:=4
else turn:=dir;
end;

Procedure move;
Begin
Case dir of
1 : inc(r.y);
2 : inc(r.x);
3 : dec(r.y);
4 : dec(r.x);
end;
end;

Function inbounds:boolean;
Begin
if (r.x>lx) or (r.x<0) or (r.y>ly) or (r.y<0) then
begin
inbounds:=true;
field[r.x,r.y]:=dir;
Case dir of
1 : dec(r.y);
2 : dec(r.x);
3 : inc(r.y);
4 : inc(r.x);
end;
end
else inbounds:=false;
end;

Procedure verify(d:integer);
Var x,y:integer;
Begin
x:=r.x;
y:=r.y;
Case d of
1 : inc(y);
2 : inc(x);
3 : dec(y);
4 : dec(x);
end;
if field[x,y]<>0 then
begin
if field[x,y]<>dir then move;
end
else move;
end;

Begin
readln(lx,ly);
While not eof(input) do
begin
fim:=false;
readln(r.x,r.y,r.o,r.o);
readln(orders);
case r.o of
'N' : dir:=1;
'E' : dir:=2;
'S' : dir:=3;
'W' : dir:=4;
end;
For p:=1 to length(orders) do
begin
case orders[p] of
'R','L' : dir:=turn(orders[p]);
'F' : begin
verify(dir);
scent:=false;
end;
end;
fim:=inbounds;
if fim then break;
end;
case dir of
1 : r.o:='N';
2 : r.o:='E';
3 : r.o:='S';
4 : r.o:='W';
end;
write(r.x,' ',r.y,' ',r.o);
if fim then writeln(' LOST')
else writeln;
end;
End.


[/pascal]

[ravingavin]

For my first ACM problem ever, I attempted to solve problem #118. From what I can see, everything seems to be correct. If there is a problem, I am almost positive that it has to do with my input. I don't really understand how input works with the "online judge". If someone could lead me in the right direction, I would appreciate it.

Code: Select all

#include <iostream>
#include <cstring>

using namespace std;

void orientation(int, int, int, int, char [], char, char *, char *, char *, int *, int *, int &, int, char *); 

int main(){

	int xlost[400];
	int ylost[400];
	char directionlost[400];
	char commandlost[100];
	int f = 0;

	char pointofloss[400];
	int boundx, boundy, x, y;
	char commands[20], direction;
	int length;
	char oppositedirection[400];


	
	cin >> boundx >> boundy >> x >>  y  >>  direction >>  commands;

	while(cin.get() != EOF){

		length = strlen(commands);

		orientation(boundx, boundy, x, y, commands, direction,  pointofloss, directionlost, commandlost, xlost, ylost, f, length, oppositedirection);

		cin >> x >> y >> direction >> commands;
	}

	return 0;

}

void orientation(int boundx, int boundy, int x, int y, char commands[], char direction, char *pointofloss, char *directionlost, char *commandlost, int *xlost, int *ylost, int &f, int length, char *oppositedirection){

	int status=0;

	for(int i=0; i<=length; i++){

		if(commands[i] != NULL){

			if(commands[i] == 'F'){

				if(direction == 'E'){
					x = x+1;
					status=0;
				}

				else if(direction == 'W'){
					x = x-1;
					status=0;
				}

				else if(direction == 'N'){
					y = y+1;
					status=0;
				}
				else if(direction == 'S'){
					y =y-1;
					status=0;
				}

				if(x > boundx){
					status=1;
					x=x-1;
				}
				if(x < 0){
					status=1;
					x=x+1;
				}
				if(y > boundy){
					status=1;
					y=y-1;
				}
				if(y < 0){
					status=1;
					y=y+1;
				}

				for(int c = 0; c <f; c++){
			
					if(commandlost[c] == commands[i] && xlost[c]==x && ylost[c]==y && (directionlost[c]==direction || oppositedirection[c])){
						status=0;
						x = xlost[c];
						y = ylost[c];

						if(directionlost[c]==direction)
							direction = directionlost[c];

						else if(oppositedirection[c]==direction)
							direction = oppositedirection[c];
					}

				}
				if(status==1){
					xlost[f] = x;
					ylost[f] = y;
					directionlost[f] = direction;
					commandlost[f] = commands[i];
					if(direction == 'N' || direction == 'S'){
					
						if(x+1 > boundx){
							oppositedirection[f] = 'E';
						}

						else if(x-1 < 0){
							oppositedirection[f] = 'W';
						}
						else if(x-1 > 0 && x+1 < boundx){
							oppositedirection[f]='$';
						}
					}

					else if(direction == 'E' || direction == 'W'){

						if(y+1 > boundy){
							oppositedirection[f] = 'N';
						}

						else if(y-1 < 0){
							oppositedirection[f] = 'S';
						}
						else if(y-1 > 0 && y+1 < boundy){
							oppositedirection[f]='$';
						}
					}
					f++;
					break;
				}

			}
			if(commands[i] == 'L'){

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

				else if(direction == 'W')
					direction = 'S';

			}
			if(commands[i] == 'R'){

				if(direction == 'N')
					direction = 'E';

				else if(direction == 'E')
					direction = 'S';

				else if(direction == 'S')
					direction = 'W';

				else if(direction == 'W')
					direction = 'N';
			}
		}

	}

	cout << x << " " << y << " " << direction;


	if(status==1)
		cout << " LOST" << endl;

	else if(status==0)
		cout << endl;

	status=0;
		
}

P.S. I am aware that my program is not efficient and all that other stuff; I just want to solve the problem. I'm a C++ newb .

Thanks for your help,

GCS

[xbeanx]

The problem here is not obvious at first. Try using the following input:

Code: Select all

40 50
0 0 E
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

I think then you'll understand why you got WA.

So how do you fix it? Simply increase your commands[] buffer to accomodate such long command sequences.

PS, about the efficiency issue: theres nothing wrong with your code, but there is a lot of stuff in there that doesn't need to be. I don't even understand half of it (like what is the variable oppositeddirection[] for?)

But at least you solved the problem!!

[ravingavin]

Let me explain what oppositedirection[] was used for. Say the boundaries of your square are 3,3. Well if you start at (3, 0) facing N and then go FFFF the first time then your robot will be lost. But since the last robot leaves a scent, you have to make sure that the following robots won't fall off at both (3,3) N as well as (3,3) E. So I used oppositedirection to save the other direction (E) that the robot cannot fall off of (if it existed).

Thanks for your help. I thought that the max input of commands was 20; instead, it happened to be 100. Simple mistake but costly error.


Thanks again for your help!!

GCS

[xbeanx]

I see what the variable was for now.

In mine, I just used a nxn boolean matrix, so I did not have to do such a check. Yours was actually more efficient in that regard, but since boolean values do not take much memory, I decided to use a matrix.