Problem A
Robot maps |
The ACM factory produces and stores
very dangerous products. This is why no human operator is allowed to enter the
store room and only specialised robots can access the place to store new
products or to retrieve them for their sell. The ACM factory is testing a movil
robot which is able to build a partial map of the continuously changing
environment of the store.
The robot can be initially placed at
any position of the store. Before starting moving, the robot initialises every
cell of its map as a ?, which means unknown cell. In the beginning, the robot knows that
its starting cell is empty and records this information into its map. Then, the robot reads its
four sensors, which will return the state (X if occupied, 0 if empty) of
the four cells around it: NORTH, EAST, SOUTH, WEST. This information is
properly recorded in the robots map. Then it will move to the first* unvisited
free cell and repeat the process until it can not move any further because all
the cells around it are occupied or have already been visited. Then the robot
outputs its partial map of the store.
(*) The order used by the robot to select its movements is clockwise,
starting from the North orientation.
The input file consists of a series
of sets each containig 2+N lines. First line specifies the size of the
map, i.e. two integers N and M separated by one space, where 0 < N <= 10 and 0 < M <= 10. The second line
specifies the starting point of the robot in the map, i.e. two integers x_ini and y_ini separated by one space,
where 1 <= x_ini <= N and 1 <= y_ini <= M .
In each of the next N lines there must be M characters X or 0
separated by one space, where X represents obstacles and 0 represents empty
squares. The map must be a correct one, which means the initial position of the
robot must be always an empty cell. The end of the file is reached the size of
the next map is N=0 and M=0.
The application outputs an empty
line, followed by the robot map, an empty line, and a line containing a message
of the movements needed to reach that map.
The robot map must be shown
using the next format:
|---|---|
M
|---|
| s | s |
M
| s |
|---|---|
M
|---|
| s | s |
M
| s |
|---|---|
M
|---| s
Ξ
{X, 0, ?}
N
|---|---|
M
|---|
| s | s |
M
| s |
|---|---|
M
|---|
5 5
1 3
X X 0 0 X
X X 0 0 X
X 0 X 0 X
X 0 0 0 X
X X X X X
5 5
1 1
0 0 X X X
X X 0 0 X
X 0 0 0 X
X 0 0 0 X
X X X X X
0 0
|---|---|---|---|---|
| ? | X | 0 | 0 | X |
|---|---|---|---|---|
| ? | X | 0 | 0 | X |
|---|---|---|---|---|
| X | 0 | X | 0 | X |
|---|---|---|---|---|
| X | 0 | 0 | 0 | X |
|---|---|---|---|---|
| ? | X | X | X | ? |
|---|---|---|---|---|
NUMBER OF MOVEMENTS: 7
|---|---|---|---|---|
| 0 | 0
| X | ? | ? |
|---|---|---|---|---|
| X | X
| ? | ? | ? |
|---|---|---|---|---|
| ? | ?
| ? | ? | ? |
|---|---|---|---|---|
| ? | ?
| ? | ? | ? |
|---|---|---|---|---|
| ? | ?
| ? | ? | ? |
|---|---|---|---|---|
NUMBER OF MOVEMENTS: 1