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
|
using namespace std;
typedef pair<int, int> Pair;
const int MAX_N = 9 + 3;
int sx, sy, tx, ty; string sd; int maze[MAX_N][MAX_N][4]; vector<Pair> ans;
int dX[4] = {1, 0, -1, 0}, dY[4] = {0, -1, 0, 1};
struct { int x, y, d; }; Point pre[MAX_N][MAX_N][4];
const char* dir = "SWNE"; const char* adir = "LFR";
int did(char c) { return strchr(dir, c) - dir; } int adid(char c) { return strchr(adir, c) - adir; }
bool bfs() { queue<Point> que; int x, y, d, fd = did(sd[0]); int nx = sx + dX[fd], ny = sy + dY[fd]; pre[nx][ny][fd] = (Point) {sx, sy, fd}; que.push((Point) {nx, ny, fd});
while (!que.empty()) { Point p = que.front(); que.pop(); x = p.x, y = p.y, d = p.d; if (x == tx && y == ty) break;
for (int i = 0; i < 3; i++) { if (!((maze[x][y][d] >> i) & 1)) continue; fd = d; if (i == 0) fd = (fd - 1 + 4) % 4; else if (i == 2) fd = (fd + 1) % 4;
int nx = x + dX[fd], ny = y + dY[fd]; Point& pp = pre[nx][ny][fd]; if (pp.x == 0 && pp.y == 0 && pp.d == 0) { pp = (Point) {x, y, d}; que.push((Point) {nx, ny, fd}); } } }
for (int i = 0; i < 4; i++) { Point pp = pre[tx][ty][i]; if (pp.x == 0 && pp.y == 0 && pp.d == 0) continue; Point p = (Point) {tx, ty, i}; while (p.x != sx || p.y != sy) { ans.push_back(Pair(p.x, p.y)); p = pre[p.x][p.y][p.d]; } ans.push_back(Pair(sx, sy)); reverse(ans.begin(), ans.end()); return true; } return false; }
int main() { string name, ad; int x, y; while (cin >> name && name != "END") { memset(maze, 0, sizeof(maze)); memset(pre, 0, sizeof(pre)); ans.clear();
cin >> sx >> sy >> sd >> tx >> ty; while (cin >> x && x) { cin >> y; while (cin >> ad && ad != "*") { for (int i = 1; i < ad.size(); i++) { maze[x][y][did(ad[0])] |= 1 << adid(ad[i]); } } }
bool res = bfs(); cout << name << endl; if (res) { for (int i = 0; i < ans.size(); i++) { if (i % 10 == 0) cout << " "; cout << "(" << ans[i].first << "," << ans[i].second << ")"; if (i != ans.size() - 1) cout << ((i + 1) % 10 == 0 ? 'n' : ' '); } cout << endl; } else { cout << " No Solution Possible" << endl; } } return 0; }
|
近期评论