## 824 - Coast Tracker

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

### 824 - Coast Tracker

An easy problem, but what's wrong with my program?
can anyone tell me? thanks a lot.
[cpp]#include <stdio.h>

int dire[8][2]={{1,0},{1,-1},{-1,0},{-1,-1},{0,-1},{-1,1},{0,1},{1,1}};
int start[8]={6,7,0,1,2,3,4,5};

struct Tdata{
int x,y,type;
}data[8];
int x,y,dir;

bool island(int x,int y)
{
int i;
for (i=0;i<8;i++)
if (data.x==x&&data.y==y)
if (data.type==1) return true;
else return false;
return false;
}

int main()
{
int i,nx,ny,ndir;
while (1){
scanf("%d",&y);
if (y==-1) break;
scanf("%d%d",&x,&dir);
for (i=0;i<8;i++) scanf("%d%d%d",&data.y,&data.x,&data.type);
for (i=0;i<8;i++){
ndir=(i+start[dir])%8;
nx=x+dire[ndir][0],ny=y+dire[ndir][1];
if (island(nx,ny)){
printf("%d\n",ndir);
break;
}
}
}
return 0;
}
[/cpp]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Did u consider this:-
the robot will always start its job in a square of the coast, with the sea at its right; therefore, the coast will be tracked in a counter clockwise direction
I think u should test these inputs
• Input:
21 27 4
21 28 1
20 28 1
20 27 0
20 26 1
21 26 1
22 26 0
22 27 1
22 28 0
21 27 4
21 28 0
20 28 1
20 27 1
20 26 1
21 26 0
22 26 1
22 27 1
22 28 1
21 27 3
21 28 1
20 28 1
20 27 1
20 26 0
21 26 1
22 26 0
22 27 1
22 28 1
-1
And the output will be
• Output:
3
5
4
I hope this works....
Ami ekhono shopno dekhi...
HomePage

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Try this set of input.

INPUT

Code: Select all

``````
22 25 6
22 26 1
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 0
21 24 1
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 1
21 24 1
22 24 0
23 24 0
23 25 0
23 26 0

22 25 0
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 1
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 1
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 1
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 1
21 24 1
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 0
21 26 1
21 25 0
21 24 1
22 24 0
23 24 0
23 25 0
23 26 1

22 25 7
22 26 1
21 26 1
21 25 0
21 24 1
22 24 0
23 24 0
23 25 0
23 26 0

22 25 0
22 26 0
21 26 0
21 25 1
21 24 0
22 24 1
23 24 0
23 25 0
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 0
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 0
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 0

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 2
22 26 0
21 26 1
21 25 1
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 1
22 26 1
21 26 1
21 25 1
21 24 0
22 24 1
23 24 1
23 25 0
23 26 0

22 25 0
22 26 0
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 1
22 26 0
21 26 0
21 25 1
21 24 1
22 24 1
23 24 1
23 25 0
23 26 0

22 25 2
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 0

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 1
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 1
22 26 0
21 26 1
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 0

22 25 1
22 26 0
21 26 0
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 0

22 25 5
22 26 0
21 26 1
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 0

22 25 5
22 26 0
21 26 1
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 2
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 2
22 26 0
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 1
21 25 1
21 24 0
22 24 0
23 24 1
23 25 1
23 26 1

22 25 5
22 26 1
21 26 1
21 25 0
21 24 1
22 24 1
23 24 1
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 0
23 24 0
23 25 1
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 1
22 24 1
23 24 1
23 25 0
23 26 1

22 25 3
22 26 0
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 1
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 0

22 25 6
22 26 0
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

22 25 6
22 26 1
21 26 0
21 25 1
21 24 0
22 24 0
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 0
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 0
22 24 1
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 0

22 25 0
22 26 1
21 26 1
21 25 1
21 24 1
22 24 1
23 24 0
23 25 0
23 26 1

22 25 7
22 26 0
21 26 1
21 25 1
21 24 1
22 24 0
23 24 1
23 25 1
23 26 0

22 25 5
22 26 1
21 26 1
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 1
23 24 0
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 0
23 24 1
23 25 0
23 26 1

22 25 5
22 26 0
21 26 1
21 25 0
21 24 0
22 24 1
23 24 1
23 25 1
23 26 1

22 25 4
22 26 1
21 26 0
21 25 0
21 24 0
22 24 0
23 24 0
23 25 1
23 26 1

-1

``````
OUTPUT

Code: Select all

``````
6
6
6
6
6
7
7
0
2
2
2
1
0
7
6
7
7
0
2
2
2
2
4
4
3
2
1
0
1
2
3
3
3
1
1
5
5
3
3
2
2
6
6
6
6
5
3
3
3
6
6
6
6
0
0
0
0
7
5
4
4
5
4
6

``````

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:
Jan,

I don't think your sample input makes sense. For instance, your first test case looks like this:

110
011
110

with direction = 4. However, this is impossible - the direction must be 5 (giving a previous square of [0,2]). If the direction were indeed 4 then we would have a non-optimal previous square of [1, 2].

Of course this is assuming our robot always moves perfectly, but for this problem I think that is a safe assumption

-Andrew

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
The problem states that..
Given the current position and direction of the robot, and a percept of the surrounding world, decide the direction of the next move. Note that you are not being asked to program the whole coasttracking software; you are just programming a part of it. The direction must be computed in such a way that an iterative call of the program, with percepts from an environment as the one described, would allow the robot to track the coast.
I think I just made a part of the whole system...
Ami ekhono shopno dekhi...
HomePage

kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm

### reply to daveon

daveon on post gave the test cases with the answers that are assumed to be right - actually - they are wrong (at least from the point of Online Judge) - because my program was accepted although it on approx 10% cases gave the different answers.

My strategy was to consider the nearest direction on the clockwise (and if for the current number of steps it doesn't exist - so seek in the counterclockwise direction from the initial position/direction) with the follwing condition: the land should be in the direction under considertion and the water should be in the immediate neigbourgh. Note - thet if this is tru for the intial direction then - one should reject it and seek new one...

Well - it worked for me - at least...

Daveon - pleas - be kind and review your data...

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
My test data corresponds to Figure 1 in the problem.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am

### Re: reply to daveon

kwedeer wrote:daveon on post gave the test cases with the answers that are assumed to be right - actually - they are wrong (at least from the point of Online Judge) - because my program was accepted although it on approx 10% cases gave the different answers.
And you think you know the IO of the judge? Geese, I'm just trying to help.

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
for the following configuration:

Code: Select all

``````1   1   0
0  [4]  1      (4 is the current direction)
1   1   0
``````
why the next move is 3 not 6? similarly,

Code: Select all

``````1   1   1
1  [3]  1
0   1   0
``````
why the next move is 6 not 4?