Page 2 of 5
Posted: Fri Jul 19, 2002 11:35 am
by 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
118 - Mutant Flatworld Explorers
Posted: Fri Aug 09, 2002 12:33 pm
by 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]
Re: 118
Posted: Fri Aug 09, 2002 4:55 pm
by 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.
WA
Posted: Sun Sep 22, 2002 6:48 pm
by Subeen
my code is here:
[c]
code removed
[/c]
Posted: Sun Sep 22, 2002 8:59 pm
by 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.
thanks
Posted: Thu Sep 26, 2002 7:14 pm
by Subeen
thanks for help

i got it AC
P 118, WA and no clue as to why
Posted: Wed Nov 20, 2002 5:01 am
by 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]
Posted: Fri Nov 22, 2002 12:48 pm
by 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.
Posted: Fri Nov 22, 2002 2:20 pm
by JTK1996
Hi Olorin,
I got accepted now, so my feelin
Posted: Fri Nov 22, 2002 4:02 pm
by 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 !
Problem 118(Pascal) I really don't know why I get WA...
Posted: Fri Jun 27, 2003 1:43 am
by 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]
Problem 118: Mutant Flatworld Explorers
Posted: Sun Sep 14, 2003 11:56 pm
by 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
Posted: Wed Sep 17, 2003 1:27 pm
by 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!!

Re: array oppositedirection[]
Posted: Wed Sep 17, 2003 7:04 pm
by 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
Posted: Fri Sep 19, 2003 4:16 pm
by 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.