Page 1 of 1
824 - Coast Tracker
Posted: Wed Sep 22, 2004 5:48 pm
by zzzzzddddd
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]
Posted: Wed Jun 22, 2005 11:16 pm
by Jan
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
I hope this works....
Posted: Fri Jul 22, 2005 10:39 pm
by daveon
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
Posted: Mon Aug 08, 2005 6:58 am
by drewsome
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
Posted: Wed Aug 17, 2005 3:01 pm
by Jan
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...
reply to daveon
Posted: Tue May 09, 2006 11:14 pm
by kwedeer
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...
Posted: Sun May 14, 2006 10:04 pm
by daveon
My test data corresponds to Figure 1 in the problem.
Re: reply to daveon
Posted: Fri Jun 23, 2006 5:04 am
by 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.
Posted: Tue Jan 09, 2007 3:10 pm
by Donotalo
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,
why the next move is 6 not 4?
please help me to understand!
(these examples are taken from Jan's sample input 1 and 3, respectively.)