[UVA] 314 - Robot
Robot
| Robot |
The Robot Moving Institute is using a robot in their local store to transport
different items.
Of course the robot should spend only the minimum time necessary when
travelling from one place
in the store to another. The robot can move only along a straight line (track).
All tracks form a
rectangular grid. Neighbouring tracks are one meter apart. The store is a
rectangle 
meters
and it is entirely covered by this grid. The distance of the track closest
to the side of the store is
exactly one meter. The robot has a circular shape with diameter equal
to 1.6 meter. The track
goes through the center of the robot. The robot always faces north, south,
west or east. The tracks
are in the south-north and in the west-east directions. The robot can
move only in the direction
it faces. The direction in which it faces can be changed at each track
crossing. Initially the robot
stands at a track crossing. The obstacles in the store are formed from
pieces occupying 
on the ground. Each obstacle is within a 
square formed by the
tracks. The movement of the
robot is controlled by two commands. These commands are GO and TURN.
The GO command has one integer parameter 
{1,2,3}. After
receiving this command the robot moves n meters in the direction it faces.
The TURN command has one parameter which is either left or right. After receiving this command the robot changes its orientation by 90o in the direction indicated by the parameter.
The execution of each command lasts one second.
Help researchers of RMI to write a program which will determine the minimal time in which the robot can move from a given starting point to a given destination.
Input
The input file consists of blocks of lines. The first line of each block
contains two integers
and 
separated by one space. In each of the next M
lines there are N numbers
one or zero separated by one space. One represents obstacles and zero
represents empty squares.
(The tracks are between the squares.) The block is terminated by a line
containing four positive
integers 
each followed by one space and the word indicating
the orientation of the
robot at the starting point. 
, 
are the coordinates of the square
in the north-west corner of
which the robot is placed (starting point). 
, 
are the coordinates
of square to the north-west
corner of which the robot should move (destination point). The orientation
of the robot when it
has reached the destination point is not prescribed. We use
(row, column)-type coordinates, i.e.
the coordinates of the upper left (the most north-west) square in the
store are 0,0 and the lower
right (the most south-east) square are M - 1, N - 1. The orientation is
given by the words north
or west or south or east. The last block contains only
one line with N = 0 and M = 0.
Output
The output file contains one line for each block except the last block in the input file. The lines are in the order corresponding to the blocks in the input file. The line contains minimal number of seconds in which the robot can reach the destination point from the starting point. If there does not exist any path from the starting point to the destination point the line will contain -1.
Example
Sample Input
9 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 7 2 2 7 south 0 0
Sample Output
12
題目描述：
機器人從起點走到終點的最少時間為何？同時不會經過黑色方格的邊緣，順逆時針旋轉 90 度改變方向需要 1 秒，
而朝著這個方向前進也需要 1 秒。
題目解法：
多考慮一個當前方向的狀態，直接使用 BFS 即可。
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
int n, m;
int g[105][105];
int dx[] = {-1,0,1,0};//NESW
int dy[] = {0,1,0,-1};
int used[105][105][4] = {};
void bfs(int sx, int sy, int ex, int ey, int d) {
if(sx == ex && sy == ey) {
puts("0");
return ;
}
memset(used, 0, sizeof(used));
int x, y;
int i, j, k, tx, ty, td;
used[sx][sy][d] = 1;
queue<int> X, Y, D;
X.push(sx), Y.push(sy), D.push(d);
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
d = D.front(), D.pop();
tx = x+dx[d], ty = y+dy[d];
for(i = 1; i <= 3; i++) {
if(tx < 1 || ty < 1 || tx >= n || ty >= m)
break;
if(g[tx][ty]) continue;
if(used[tx][ty][d] == 0) {
used[tx][ty][d] = used[x][y][d]+1;
X.push(tx), Y.push(ty), D.push(d);
}
tx += dx[d], ty += dy[d];
}
tx = x, ty = y;
td = (d+1)%4;//right rotate
if(used[tx][ty][td] == 0) {
used[tx][ty][td] = used[x][y][d]+1;
X.push(tx), Y.push(ty), D.push(td);
}
td = (d+3)%4;//left rotate
if(used[tx][ty][td] == 0) {
used[tx][ty][td] = used[x][y][d]+1;
X.push(tx), Y.push(ty), D.push(td);
}
if(used[ex][ey][0] || used[ex][ey][1] || used[ex][ey][2] || used[ex][ey][3])
break;
}
int ret = 0;//ret-1 = -1 = can't research
for(i = 0; i < 4; i++) {
if(used[ex][ey][i]) {
ret = used[ex][ey][i];
}
}
printf("%d\n", ret-1);
}
int main() {
while(scanf("%d %d", &n, &m) == 2 && n) {
int i, j, k;
memset(g, 0, sizeof(g));
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
scanf("%d", &k);
if(k) {
g[i-1][j-1] = 1;
g[i-1][j] = 1;
g[i][j-1] = 1;
g[i][j] = 1;
}
}
}
char dir[10];
int sx, sy, ex, ey, d;
scanf("%d %d %d %d %s", &sx, &sy, &ex, &ey, dir);
if(dir[0] == 'n') d = 0;
if(dir[0] == 'e') d = 1;
if(dir[0] == 's') d = 2;
if(dir[0] == 'w') d = 3;
bfs(sx, sy, ex, ey, d);
}
return 0;
}