118 - Mutant Flatworld Explorers

[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

[emotional blind]

is there any critical input/output for 118
i got wa all the time
plz help me

[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

[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.

[ImLazy]

Hope this helps.http://online-judge.uva.es/board/viewto ... 1416#31416

[emotional blind]

Thanks a lot...
I got AC

[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

[teni_teni]

Maybe you already got AC...
If not, try this:

Code: Select all

1 1
0 0 N
LF

[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.

[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

[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

[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");}
}
}

[himel85]

I got ma error!!! thanx 2 all

[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~ : )

[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. : )