## 118 - Mutant Flatworld Explorers

Moderator: Board moderators

Neo
New poster
Posts: 3
Joined: Thu Jul 18, 2002 1:17 pm
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
New poster
Posts: 7
Joined: Fri Aug 09, 2002 12:26 pm
Location: Poland

### 118 - Mutant Flatworld Explorers

[pascal]
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
while not eof do begin
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;

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;

end;
end.[/pascal]

Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

### Re: 118

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:

### WA

my code is here:

[c]
code removed
[/c]
Last edited by Subeen on Tue Jul 20, 2004 1:47 pm, edited 1 time in total.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:

### thanks

thanks for help i got it AC

Olorin
New poster
Posts: 8
Joined: Sun Nov 03, 2002 3:39 pm

### P 118, WA and no clue as to why

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

[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)
{
switch(oldd)
{
default: break;
}//SWITCH
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]
-- Elen Sila Lumenn' Omentielvo --

JTK1996
New poster
Posts: 4
Joined: Thu Nov 21, 2002 3:10 pm
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
New poster
Posts: 4
Joined: Thu Nov 21, 2002 3:10 pm
Hi Olorin,
I got accepted now, so my feelin

Olorin
New poster
Posts: 8
Joined: Sun Nov 03, 2002 3:39 pm
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 !
-- Elen Sila Lumenn' Omentielvo --

pheres
New poster
Posts: 1
Joined: Sun May 18, 2003 2:14 am
Location: Portugal

### Problem 118(Pascal) I really don't know why I get WA...

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
While not eof(input) do
begin
fim:=false;
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
New poster
Posts: 21
Joined: Sun Sep 14, 2003 11:44 pm
Location: USA
Contact:

### Problem 118: Mutant Flatworld Explorers

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 .

GCS

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
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
New poster
Posts: 21
Joined: Sun Sep 14, 2003 11:44 pm
Location: USA
Contact:

### Re: array oppositedirection[]

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.