Page 3 of 5
118 Runtime Error frustration
Posted: Tue Sep 14, 2004 9:23 am
by itsme86
This is my code:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3
typedef struct
{
int x;
int y;
int dir;
int lost;
} ROBOT;
void turn_right(ROBOT *r);
void turn_left(ROBOT *r);
int go_north(ROBOT *);
int go_east(ROBOT *);
int go_south(ROBOT *);
int go_west(ROBOT *);
typedef struct
{
char ch;
int (*func)(ROBOT *);
} DIRECTION;
DIRECTION dirs[4] =
{
{ 'N', go_north },
{ 'E', go_east },
{ 'S', go_south },
{ 'W', go_west }
};
ROBOT *robots = NULL;
int nrobots = 0;
int maxx, maxy;
int main(void)
{
ROBOT *r;
char buf[100], *p, ch;
fgets(buf, sizeof(buf), stdin);
maxx = atoi(buf);
maxy = atoi(strchr(buf, ' ')+1);
for(;;)
{
robots = realloc(robots, sizeof(ROBOT)*(nrobots+1));
r = &robots[nrobots++];
fgets(buf, sizeof(buf), stdin);
buf[strlen(buf)-1] = '\0';
if(feof(stdin))
{
nrobots--;
break;
}
r->x = atoi(buf);
r->y = atoi((p = strchr(buf, ' ')+1));
ch = *(strchr(p, ' ')+1);
switch(ch)
{
case 'N': r->dir = NORTH; break;
case 'E': r->dir = EAST; break;
case 'S': r->dir = SOUTH; break;
case 'W': r->dir = WEST; break;
}
fgets(buf, sizeof(buf), stdin);
buf[strlen(buf)-1] = '\0';
for(r->lost = 0, p = buf;*p && !r->lost;++p)
{
switch(*p)
{
case 'R': turn_right(r); break;
case 'L': turn_left(r); break;
case 'F': r->lost = dirs[r->dir].func(r); break;
}
}
}
for(r = robots;r-robots < nrobots;++r)
printf("%d %d %c%s\n",
r->x, r->y, dirs[r->dir].ch, r->lost?" LOST":"");
return 0;
}
void turn_right(ROBOT *r)
{
if(++r->dir > 3)
r->dir = 0;
}
void turn_left(ROBOT *r)
{
if(--r->dir < 0)
r->dir = 3;
}
int has_neighbor(ROBOT *robot)
{
ROBOT *r;
for(r = robots;r-robots < nrobots;++r)
if(r != robot && r->x == robot->x && r->y == robot->y)
return 1;
return 0;
}
int go_north(ROBOT *r)
{
if(r->y+1 > maxy)
return !has_neighbor(r);
r->y++;
return 0;
}
int go_east(ROBOT *r)
{
if(r->x+1 > maxx)
return !has_neighbor(r);
r->x++;
return 0;
}
int go_south(ROBOT *r)
{
if(r->y-1 < 0)
return !has_neighbor(r);
r->y--;
return 0;
}
int go_west(ROBOT *r)
{
if(r->x-1 < 0)
return !has_neighbor(r);
r->x--;
return 0;
}
But the judge says there's a runtime error. The code works correctly on my computer with the sample input shown in the problem description. Am I incorrect in assuming that the input will be valid? Is blindly trusting the input with strchr() the source of my problem here? Or is dynamic memory allocation forbidden maybe?
I'm brand new to this site so any information you can give me would be greatly appreciated!
Thank you
118-wa
Posted: Sat Feb 05, 2005 3:27 pm
by emotional blind
is there any critical input/output for 118
i got wa all the time
plz help me
118 WA: wtf
Posted: Sun Feb 06, 2005 4:01 am
by jonaskoelker
I get WA for problem 118, which frustrates me quite a bit, since it sounds deceptively simple. I think I've read the problem carefully enough, but I might be wrong. The only 'trick' I see is the fall-over-the-edge logic, which I understand as:
next.point = getmove(current.point)
if (next.point is inside bounds) current.point = next.point;
else if (has scent) do nothing;
else { fall over; set scent(current.point); }
Is this correct?
If so, where's my implementation off?
Any help will be greatly appreciated.
Code: Select all
# include <stdio.h>
# include <stdlib.h>
static const char angles [] = "NESW";
enum bool { false, true };
enum angle { north, east, south, west };
struct point { short x, y; };
struct bot { struct point p; enum angle angle; enum bool lost; };
struct hash { struct hash * next; struct point p; };
static struct point forward (struct bot bot)
{
struct point p = bot.p;
switch (bot.angle)
{
case north: ++ p.y; break;
case east : ++ p.x; break;
case south: -- p.y; break;
case west : -- p.x; break;
}
return p;
}
# define HASHSIZE 31
# define HASH(p) (((p).x * 53 + (p).y) % HASHSIZE)
static struct hash * scents [HASHSIZE];
# define LEFT(b) (((b).angle - 1) % 4)
# define RIGHT(b) (((b).angle + 1) % 4)
int main (void)
{
struct point max;
struct bot bot;
scanf ("%hd %hd", & max.x, & max.y);
while (
3 == scanf (
"%hd %hd %1[NESW]",
& bot.p.x, & bot.p.y, (char *) & bot.angle))
{
int i, ch;
bot.lost = false;
for (i = 0; i < 4; ++i)
if ((char) bot.angle == angles[i])
bot.angle = i;
while (getchar () != '\n');
while ((ch = getchar ()) == 'F' || ch == 'R' || ch == 'L')
if (!bot.lost) switch (ch)
{
case 'F':
{
struct point p = forward (bot);
if (p.x >= 0 && p.x <= max.x && p.y >= 0 && p.y <= max.y)
bot.p = p;
else
{
struct hash * hash = scents[HASH (p)];
for (; hash; hash = hash -> next)
if (hash -> p.x == p.x && hash -> p.y == p.y)
break;
if (hash == NULL) /* if unscented */
{
/* insert new scent */
hash = malloc (sizeof * hash);
hash -> p = p;
hash -> next = scents [HASH (p)];
scents[HASH (p)] = hash;
bot.lost = true;
printf (
"%hd %hd %c LOST\n",
bot.p.x, bot.p.y, angles[bot.angle]);
}
}
}
break;
case 'R': bot.angle = RIGHT (bot); break;
case 'L': bot.angle = LEFT (bot); break;
}
if (!bot.lost)
printf ("%hd %hd %c\n", bot.p.x, bot.p.y, angles[bot.angle]);
}
return 0;
}
-- Jonas
Posted: Sun Feb 06, 2005 6:15 am
by ImLazy
This is the fall-over-the-edge logic:
Code: Select all
if(next step is Not fall-over)
go to next step;
else if(current position has scent)
do nothing;
else
fall over and leave a scent;
Pay attention: if current position has a scent, then the instruction to fall over toward any direction is ignored. For example: the upper-right point is (5,3), and there is a scent at (5,3). Then when a robot stand at (5,3) both going toward North and toward East will be ignored.
Hope this helps.
Posted: Sun Feb 06, 2005 6:30 am
by ImLazy
Posted: Wed Feb 09, 2005 7:58 am
by emotional blind
Thanks a lot...
I got AC
thanks...
Posted: Fri Feb 11, 2005 6:14 am
by jonaskoelker
To ImLazy: thanks for you reply. Unless I'm mistaken, your suggested logic is the same as mine, except that the first condition is doubly negated ('if not not ...'). Of course, I could very well be mistaken, in which case: could you point out which part of the code is wrong?
To everyone: it's driving me crazy. I'm hoping that someone with AC could be so kind as to run the following (randomly generated) input through their solution and post the output.
Code: Select all
20 20
5 11 E
FFFRFLFFFLFFRFRRFLR
15 7 S
RRLRRLLLLLLLLLLFRRRFFFRRLRL
4 17 N
LFRRLRRLLFLRRFFRFRLL
18 7 W
LFLRRRRRFFLLRFFFR
7 3 W
LLFRFFRRRLRFLFRFRRL
9 7 E
FLLRFRFFRRLLLLRRLLLFRFRRRRFLLLLRFLFFFRF
0 20 N
LFFFLFFLRLLFRRFRRLRFLLF
1 4 W
RRFRLFLFLR
5 4 S
LRFLFRFFFL
16 7 S
LFFRFFRLRFFRFL
9 4 S
FLRRLLLRLFFLLFR
5 19 E
RRLLRRLFLLFLLRFFLRLRRLFRLFLFFLRLLFRRRF
4 5 N
LLFRLRRLRLFLLRFRRRRLFRLF
7 12 N
RLFFFLRLLRFRLRLR
8 16 S
RFLFFRLLRFFLLL
6 7 N
LLLFLLRFFFLFLLRF
4 9 S
RLRLFFFRRLRLLLRFLLRRRRLRRRR
3 18 S
RLLFRFRFRLFRFFLFFRRRLRLLRRRFFRRRRLRF
9 9 N
LLFLRLLLLLFRFFRLRL
16 11 W
LFFFLLLRRFRLFLRLFFFLRRFFLLFRRFRF
3 17 N
LLLRRFFFLLLFL
18 3 S
FLLFRLFRFR
3 1 W
LFRFRRFFLLRFRLLFRRRLFRLRFRRLFLLRRRF
1 5 N
FLLLLFRFFLRRLRLRRLF
19 18 W
RLLRLFFFLRFRFFLFRLFLRFRFRFLFRLFFL
12 5 S
LLRRFFRRLFLLRRRFRFLFRLLFLFRRFLFRLFRRRFL
12 10 W
RFLFRFFLFLFFFFLF
3 12 N
RRLRLFFRRFFLLLFFRFFLLLRRLL
9 11 W
FLRFFRRRLFLFFFLLLL
5 18 N
LLFRRFRRFRRFLFLRFFRRLLLRFLRLRRFRRLRRLL
17 2 N
LRFRRFFFLFFLLLRRLRFRLRLR
5 7 W
FRFRRLLRRL
16 16 N
RRRLFRLFRLLFFFRFFLFRLFLFFFFRF
3 6 W
RRFRRFLFRFLFRLLFFR
20 11 N
LRRFLFFFRFRFLRFFLLRLLLFRRFRLRR
13 18 S
FRRLFRLFLFFRRRLRLRFRFF
3 3 S
FFLFFFRLLRRRF
11 17 W
LLFRLFRFLLRRLLRRLLLLLFFF
8 17 W
LLFRFFLFFFLRFRFLLLRF
18 12 S
LLFLFRLFLFLRLF
18 11 W
RRFFLRRRFLFLLLRLFFRFLRLRFRFRFLRF
14 15 E
RRFLFLFRRLFFFLRRRFFFRFFFRRLFFRRFRLRL
17 20 W
LRRRFFFLFRRRRRFLRRR
2 17 N
LRRRFFFLFR
20 10 W
LRRRRLFRFRLLLRRRRR
13 8 E
RRFRLFFLRRFRLLRFFLRFRR
5 14 S
FFRFRFFRFLRLFLFRLLF
8 10 W
FFLFLRRFFRFFFRFLLRLRFFFFRFFRRFFFRRLFLL
19 1 N
FFFRFLFLLFRFRRRLFLRRRRFRRRFFLFRLRRLLLFF
4 17 E
LFFRRRLLLFRRFRLLRLFRRRRLRFLLRFFRRFLFF
13 0 E
FLLLFLLRRRR
0 4 S
LRLFRLRLFRFFLRLRFFFFLRRLLLFFFFL
13 1 W
LRLRFLRRFLFRLRFFRLRLLRFRLFLRFLLFRRR
1 10 W
RFRRRRLFRFFLRLFLFRFRFFRRLLFLFL
6 9 E
LRLLLFLLRRFFRFRRRFRRLRFRRRFFRRFRL
13 10 E
LRRRFLFLRLFRFRRRFRL
6 9 E
RLLRFRLLRL
14 1 S
FLLRRFLFRLLFFLRLFRFFRLLRFLLFFRRLFRRFF
12 15 E
LRLLRFRFFLLRRRRRRRRLRFLFFLFLR
2 20 E
RLRRRFLLFRFRFFF
7 15 E
RLLRLLRRLLFFRLFLLRLRLFLFFFRRRFLRF
16 3 N
RRRRFLRFLRFFRRRFFLFRFLRRFLFFLL
2 12 S
RFFFLLRRLRFRLFRFLLRR
7 1 N
RLLFLLLLLFLRLRLLFLFFLFRRLLFFLRLR
14 19 W
LFRFRLFLLRFLFLFRRFFFLRRFR
1 17 W
FLRLFRRFRFLFLFLRRLLRR
20 15 S
FLLLFLLRFRLFFFLFLLLL
10 7 W
LLFLFFFFFRRLRLFLRFLLLF
11 19 W
RRRFFLFFRFLRRLRLLFLFLL
19 3 W
FLFFRRLRRRFFRLRFRLRFLLFRLRRRFFRRLLRRRF
8 2 W
FFLLRLLFLRRFLLFFFRRFRFRFRLLLRLRL
14 13 N
RLRRFFLFFLLFRRFRFRRRLLLRLL
2 8 S
LFFFRFRFRLLLRLRRRL
4 18 N
LFRRFLLRFFFRLLFRLFLLLLLLLRFFRLFLFFFLLLF
20 17 E
LFLLFFLLRLLRFLFFFFLRFFRFLRRRLLRLR
8 15 S
LRLFLFRLFLRRFRLFFRLLLRRLFFRRLF
10 8 W
LLLLRFFFRRRLFRFRRRFFRFRFFLRRFFFLRFFR
4 4 S
LLRRLLFLFRLFFRRRLRLLLRLRFLR
12 7 S
FLRFLLFLRFFFLRLRFL
5 3 N
RLFLRLFRLRLLFL
0 2 S
LRLLFFFLRRRFLFFLRFLFLRFRRFRLLFL
5 4 E
RRFFRRLLFFRRLRRLLFRLFLLLLRR
11 16 S
FFLFRRFLFRRFFLFRLFRFLF
16 13 N
RFLFRLFFLLLFFRLLFLFRFFLFFFL
1 8 N
FRLRRRFFLLFL
8 10 E
LLFRFLFFRRLFRLFFLRRLFRRRLR
18 20 W
LRFFFRFRFFRFLFLFFLLRLRRLFFFLLRRF
3 6 E
LRRRLLFLFFLFRFLFRFRRLLL
20 2 N
RFRLLRLFRFFRRLFRLFLRLLLFRRF
11 9 N
FFLLLFLLLLRLRLRLFL
1 0 S
RRLRRFLLLFLFRF
15 5 N
LFLLRFFLFFFFFRFFRRLRL
0 9 E
FLRRRLRLFFFFLRLRFFLLRFRLLLLLFLLRLLLR
11 6 E
LFFFFFRLFLRLLRFF
20 13 N
FLFLFFFRLLLLRLLRFLFRLFFFLRRRFLFFLFRLF
3 6 W
FRLLRFRLFLFRRRF
7 7 W
RRRFLFLLFFRRRLRL
4 7 W
RRFFLLRRFRLRLLLLLLLLFFRRLLFFRLL
17 0 S
LLFRRRFRRFRFRLLFFFLRFFLRRLRF
10 12 S
FFRFFLFFRFLFLLFRFRRLFFLLFRRRFR
the input is generated with the following script, just in case you care, want to generate more input or w/e:
Code: Select all
#!/usr/bin/env python
# Copyright (c) 2005 Jonas Kolker
# licensed under the GNU GPL version 2 or
# (at your option) any later version
# ... google('GNU GPL')
from sys import stdout
from random import randrange, choice
dirs = "NSEW"
cmds = "FRL"
bounds = (20, 20)
print bounds[0], bounds[1]
for i in range (100):
print randrange(0, bounds[0]+1),
print randrange(bounds[1]+1),
print choice(dirs)
for i in xrange (randrange (10, 40)):
stdout.write (choice (cmds))
print
... thanks for saving me from becoming a nervous wreck
Posted: Sun Feb 13, 2005 9:46 am
by teni_teni
Maybe you already got AC...
If not, try this:
Posted: Sun Feb 13, 2005 3:39 pm
by jonaskoelker
Nope, no AC yet.
my new implementation (in C++) gets your suggested input right: "0 0 W LOST". If any one of you have gotten AC, could you do me the favor of running my test input through your solution? Thanks in advance.
just in case you want to see the new code, here is it:
Code: Select all
# include <iostream>
# include <map>
# include <set>
# include <stdio.h>
# include <string>
# include <utility>
using namespace std;
struct point: public pair <int, int> { };
enum direction { east, north, west, south };
static struct point bounds;
static map <int, int> directions;
static set <struct point> scent;
class bot
{
private:
struct point p;
int direction;
bool lost;
struct point next () const throw () {
struct point n = p;
switch (direction)
{
case east : ++n.first ; break;
case north: ++n.second; break;
case west : --n.first ; break;
case south: --n.second; break;
default: while (1) new int [16384];
}
return n;
}
static bool inside (const struct point n) throw () {
return (
n.first >= 0 and
n.first <= bounds.first and
n.second >= 0 and
n.second <= bounds.second);
}
public:
bot (const struct point _p, int theta):
p (_p), direction (theta), lost (false)
{}
bool islost () const throw () { return lost; }
void left () throw () { direction = (direction + 1) & 3; }
void right () throw () { direction = (direction + 3) & 3; }
void forward (void) throw () {
const struct point n = next ();
if (inside (n)) p = n; // if not out of bounds, goto n.firstt point
else if (scent.find (p) == scent.end ()) // else if no scent
{
scent.insert (p);
lost = true;
printf ("%d %d %c LOST\n", p.first, p.second, directions[direction]);
}
// else: (if scent) do nothing.
}
~bot () {
if (not lost)
printf ("%d %d %c\n", p.first, p.second, directions[direction]);
}
};
int main (void)
{
directions ['E'] = east ;
directions ['N'] = north;
directions ['W'] = west ;
directions ['S'] = south;
directions [east ] = 'E';
directions [north] = 'N';
directions [west ] = 'W';
directions [south] = 'S';
cin >> bounds.first >> bounds.second;
struct point start;
char theta;
while (cin >> start.first >> start.second >> theta)
{
struct bot b (start, directions[theta]);
string move;
cin >> move;
for (unsigned i = 0; i < move.size() and not b.islost(); ++i)
switch (move[i])
{
case 'L': b.left(); break;
case 'R': b.right(); break;
case 'F': b.forward(); break;
}
}
return false;
}
this page is best viewed in emacs.
output by my AC program
Posted: Sat Mar 19, 2005 11:19 am
by lantimilan
11 12 W
14 4 W
5 17 E
20 4 E LOST
10 2 S
7 9 N
0 20 W LOST
3 5 N
6 0 E
16 6 W
9 4 W
0 18 W
5 3 E
6 15 N
7 12 W
6 9 S
4 5 W
0 19 W LOST
10 6 S
20 10 S
0 18 W
19 4 S
3 1 N
3 6 S
13 12 S
9 4 E
11 9 E
5 14 S
7 14 N
1 19 E
19 1 E
4 8 E
20 12 E LOST
4 4 S
20 11 E LOST
12 13 S
5 1 W
16 16 E
13 15 N
17 12 E
18 10 S
17 13 N
20 20 N LOST
3 14 S
20 10 E LOST
10 12 S
4 14 S
4 17 S
20 4 E
6 20 N LOST
14 0 S LOST
2 0 S LOST
11 6 E
0 13 W LOST
4 6 E
14 8 E
7 9 N
15 3 E
14 14 E
2 20 N LOST
3 18 W
11 7 E
0 12 W LOST
4 0 S LOST
12 15 N
0 18 N
20 10 E
13 11 S
14 17 S
18 0 S LOST
4 2 E
16 10 E
4 7 W
4 20 N LOST
14 18 E
13 19 E
13 10 S
1 6 N
12 10 W
4 3 E
4 5 N
1 6 S
8 16 W
15 19 S
0 9 W LOST
5 15 W
15 20 N LOST
2 10 W
20 2 E LOST
13 11 N
3 0 S LOST
19 1 W
3 3 S
9 12 W
16 6 S
1 5 E
6 6 E
7 3 E
20 0 E LOST
7 7 N
possible error source
Posted: Sat Mar 19, 2005 11:21 am
by lantimilan
Here are some pitfalls I encounter for p118, seemingly trivial problem
1. What you code do if enum type var was assigned soemthing off bounds, e.g.
enum direction { S,N,E,W }; and enum direction dir = 5; what is dir+1 then?
2. is your buffer large enough? instructions are length 100 at most, coordinates are 50 at most
118 NE genius pls check my code?? its 91 line
Posted: Tue Sep 20, 2005 6:36 pm
by himel85
#include<stdio.h>
#include<string.h>
int x,y,x0,y0,l,i,j,xx[10000],yy[10000],k,lost,flag;
char p,s[105];
void main(){
scanf("%d%d",&x,&y);
for(i=0;i<10000;i++){
xx==55;yy=55;k=1;
}
while(scanf("%d %d %c\n",&x0,&y0,&p)==3){
gets(s);
l=strlen(s);
for(i=0;i<l;i++){
if(s=='R'){
if(p=='E'){p='S';}
else if(p=='N'){p='E';}
else if(p=='W'){p='N';}
else if(p=='S'){p='W';}
}
else if(s=='L'){
if(p=='E'){p='N';}
else if(p=='N'){p='W';}
else if(p=='W'){p='S';}
else if(p=='S'){p='E';}
}
else if(s=='F'){
if(p=='W'){
if(x0-1<0){
for(j=0;j<k;j++){
if((xx[j]==x0)&&(yy[j]==y0)){
lost=0;
break;
}
else{lost=1;}
}
if(lost!=0){xx[k]=x0;yy[k]=y0;k++;}
continue;
}
else{x0=x0-1;}
}
else if(p=='N'){
if(y0+1>y){
for(j=0;j<k;j++){
if((xx[j]==x0)&&(yy[j]==y0)){
lost=0;
break;
}
else{lost=1;}
}
if(lost!=0){xx[k]=x0;yy[k]=y0;k++;}
continue;
}
else{y0=y0+1;}
}
else if(p=='E'){
if(x0+1>x){
for(j=0;j<k;j++){
if((xx[j]==x0)&&(yy[j]==y0)){
lost=0;
break;
}
else{lost=1;}
}
if(lost!=0){xx[k]=x0;yy[k]=y0;k++;}
continue;
}
else{x0=x0+1;}
}
else if(p=='S'){
if(y0-1<0){
for(j=0;j<k;j++){
if((xx[j]==x0)&&(yy[j]==y0)){
lost=0;
break;
}
else{lost=1;}
}
if(lost!=0){xx[k]=x0;yy[k]=y0;k++;}
continue;
}
else{y0=y0-1;}
}
}
}
printf("%d %d %c",x0,y0,p);
if(lost!=0){printf(" LOST\n");}
else{printf("\n");}
}
}
Posted: Tue Sep 20, 2005 8:43 pm
by himel85
I got ma error!!! thanx 2 all
118(Mutant Flatworld Explorers), I can't understand the rule
Posted: Fri Aug 18, 2006 5:02 am
by mosaick2
Who can explain me about this problem?
I can't understand a sample below.
sample
3 2 N
FRRFLLFFRRFLL
Why the sample's answer is
3 3 N LOST
Could you simulate it?
Thankx, friends~ : )
I got the idea. I was misunderstood..*_*
Posted: Sat Aug 19, 2006 2:13 am
by mosaick2
Sample Input
5 3
1 1 E
RFRFRFRF
3 2 N
FRRFLLFFRRFLL <-- Second Test
0 3 W
LLFFFLFLFL <-- Next Test
Sample Output
1 1 E
3 3 N LOST
2 3 S
Frankly, I think in the second test, old robot will be replaced by new robot at last grid position just soon after the old robot was disappeared. So, I can't understand the answer.
Now, I got the idea. Actually, the old robot couldn't replace at the same test. New robot will work at next test. : )