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 N x M 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 1m x 1m on the ground. Each obstacle is within a 1 x 1 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 n in {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 consists of blocks of lines. The first line of each block contains two integers M <= 50 and N <= 50 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 B1 B2 E1 E2 each followed by one space and the word indicating the orientation of the robot at the starting point. B1, B2 are the coordinates of the square in the north-west corner of which the robot is placed (starting point). E1, E2 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 contains one line for each block except the last block in the input. The lines are in the order corresponding to the blocks in the input. 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.
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
Source
题目类型：BFS
算法分析：先将所给的障碍的位置在图中标记，后面直接调用BFS即可。注意这里要比一般的BFS多加一个方向的状态，vis[x][y][dir]表示以dir这个方向走到(x, y)这个位置的最小时间。注意BFS一定要遍历完所有合理的状态之后才能得到最终的结果！！！注意机器人是不能走边界的！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6666; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; struct node { int x, y, cnt; string cur; node (int xx, int yy, string ccur, int ccnt) : x (xx), y (yy), cur (ccur), cnt (ccnt) {} node () {} }; int g[66][66], aa[66][66], sx, sy, ex, ey, row, col; string dir; int vis[66][66][66]; map <string, int> ma; queue <node> qu; bool OK (int x, int y) { if (x >= 1 && x <= row - 1 && y >= 1 && y <= col - 1) return true; return false; } int PP (node &s, int len, int flag) { int tt = ma[s.cur]; int tx = s.x + len * dx[tt], ty = s.y + len * dy[tt]; if (!flag) return tx; else return ty; } void SS (node &tt) { for (int i = 1; i <= 3; i++) { int tx = PP (tt, i, 0), ty = PP (tt, i, 1); if (OK (tx, ty) && g[tx][ty]) return ; else if (OK (tx, ty) && !g[tx][ty] && vis[tx][ty][ma[tt.cur]] > tt.cnt + 1) { vis[tx][ty][ma[tt.cur]] = tt.cnt + 1; qu.push (node (tx, ty, tt.cur, tt.cnt + 1)); } } } node change (string s, node tt) { node res = tt; if (s == "left") { if (ma[tt.cur] == 0) res.cur = "west"; if (ma[tt.cur] == 1) res.cur = "east"; if (ma[tt.cur] == 2) res.cur = "south"; if (ma[tt.cur] == 3) res.cur = "north"; } else if (s == "right") { if (ma[tt.cur] == 0) res.cur = "east"; if (ma[tt.cur] == 1) res.cur = "west"; if (ma[tt.cur] == 2) res.cur = "north"; if (ma[tt.cur] == 3) res.cur = "south"; } res.cnt++; return res; } int minval; void bfs () { for (int i = 0; i < 66; i++) for (int j = 0; j < 66; j++) for (int k = 0; k < 66; k++) vis[i][j][k] = INF; vis[sx][sy][ma[dir]] = 0; while (!qu.empty ()) qu.pop (); qu.push (node (sx, sy, dir, 0)); while (!qu.empty ()) { node tt = qu.front (); qu.pop (); if (tt.x == ex && tt.y == ey) minval = min (minval, tt.cnt); node ta = change ("left", tt); node tb = change ("left", ta); node tc = change ("right", tt); SS (tt); SS (ta); SS (tb); SS (tc); } } int main() { ma["north"] = 0; ma["south"] = 1; ma["west"] = 2; ma["east"] = 3; // CPPFF; while (cin >> row >> col) { if (row == 0 && col == 0) break; memset (g, 0, sizeof (g)); for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) { cin >> aa[i][j]; if (aa[i][j] == 1) { g[i][j] = g[i][j+1] = g[i+1][j] = g[i+1][j+1] = 1; } } cin >> sx >> sy >> ex >> ey >> dir; minval = INF; bfs (); if (minval == INF) cout << "-1" << endl; else cout << minval << endl; } return 0; } |