[UVA] 824 - Coast Tracker
Coast Tracker
2222 AC. The Earth Space Agency (ESA)is preparing a robot mission to Planet Atlantis, discovered justone century ago. The planet was named upon the old legend of thedisappeared continent because its surface is almost entirelyoccupied by an immense sea. There are no continents in thatplanet, yet a significant part of its surface is covered by land:millions of small, unexplored islands are known to exist all overAtlantis.| Coast Tracker |
One of the goals of the mission is to build a completemap of the planets islands. As the visibility conditions are notsuitable for aerial observation, ESA decided to build a set ofrover robots specifically intended to make coast tracking by land.The idea is to leave one of these robots at one point in the coastof an island and let him autonomously discover the map of theentire coast, then come back as the robot returns to the sameplace and take it to the next island.
You are working with theteam that is programming the navigation software for these robots,and some decisions were already taken: the surface will bediscretised into squared, equal-sized areas; for simplificationpurposes, each area will be considered as being entirely coveredby land or water. Also, the robot will always start its job in asquare of the coast, with the sea at its right; therefore, thecoast will be tracked in a counter clockwise direction (see Figure1).
The robot will have a limited perception system thatwill be able to determine the kind of surface of the 8 areasneighbouring the one where the robot stands. Its movementcapabilities will also be limited: the robot will only have thepossibility of (i) rotating to one of 8 fixed directions (coded asintegers from 0 to 7, 0 being North - see Figure 2) and (ii)moving to the neighbour position in front of him. Each time therobot moves to a new position, the perception system gets a newpercept. There are no obstacles to worry about: God convenientlyarranged the islands to have smooth, sand coasts. There are lakes(e.g., A, B, C, D and E in Figure 1), but the robot must not wastetime with them: the goal is to track the seacoast only.
Given the current position and direction of the robot, and apercept of the surrounding world, decide the direction of the nextmove. Note that you are not being asked to program the wholecoasttracking software; you are just programming a part of it.The direction must be computed in such a way that an iterativecall of the program, with percepts from an environment as the onedescribed, would allow the robot to track the coast.
Your programmust be able to process several scenarios. Each scenario comprisesthe robots current position and direction, and a percept. Figure 3illustrates three hypothetical scenarios and the intended result:the direction of the next move.
Input
The input file represents several scenarios. Input for eachscenario consists of 9 lines as follows:- First line: x y d, where x and y are the (always positive) coordinates of the robots current position, and d is therobots current direction, an integer such that 0
d7 (see Figure 2); - Next 8 lines: xi yi si, where si is a number representing the surface type of the neighbouring position (xi, yi);land surface is represented by 1, and water surface by 0.
Successive values in a line are separated by one or more blanks. Theinteger -1 follows the data of the last scenario.
Output
For each given scenario, your program has to output the direction ofthe next robot's movement. Output for successivescenarios should be written in successive lines.Sample Input
22 25 222 26 021 26 121 25 121 24 122 24 123 24 123 25 123 26 021 26 121 27 120 27 120 26 120 25 021 25 122 25 122 26 022 27 021 27 021 28 020 28 120 27 120 26 121 26 122 26 022 27 022 28 0-1
Sample Output
101
Amílcar Cardoso, MIUP'2001
題目描述：
要求機器人逆時針繞著海岸走，現在給你機器人的座標，以及上一步走向的方位，
現在問你下一步進行的方位。
題目解法：
由於只知道中心點外的八個點，但又不知道座標的大小，無法貿然開陣列。
找點的時候，先從上一步反向的下一個方位(逆時針)開始搜索，
這樣才可以找到逆時針走法。
#include <stdio.h>
int main() {
int x, y, d, i, j, k;
int xi[10], yi[10], si[10];
int dx[8] = {0,-1,-1,-1,0,1,1,1};
int dy[8] = {1,1,0,-1,-1,-1,0,1};
while(scanf("%d %d %d", &x, &y, &d) == 3) {
for(i = 0; i < 8; i++)
scanf("%d %d %d", &xi[i], &yi[i], &si[i]);
int tx, ty;
for(i = d+5, j = 0; j < 8; j++, i++) {
i = (i+8)%8;
tx = x+dx[i], ty = y+dy[i];
for(k = 0; k < 8; k++) {
if(xi[k] == tx && yi[k] == ty && si[k] == 1)
break;
}
if(k != 8) {
printf("%d\n", i);
break;
}
}
}
return 0;
}