// Solution to maze problem: // // Assumes that exit to the maze is always on an // exterior wall. #include #include #include #include using namespace std; string directions = "NESW"; string readWalls() { string walls = "XXXX"; // NESW string line; // read the 4 walls that we could move towards getline (cin, line); walls[0] = line[1]; getline (cin, line); walls[3] = line[0]; walls[1] = line[2]; getline (cin, line); walls[2] = line[1]; return walls; } struct Location { int x; int y; Location (int xx, int yy): x(xx), y(yy) {} bool operator< (const Location& r) const {return x < r.x || (x == r.x && y < r.y);} bool operator== (const Location& r) const {return x == r.x && y == r.y;} void move (int dir) { static const int xoffsets[] = {0, 1, 0, -1}; static const int yoffsets[] = {1, 0, -1, 0}; x += xoffsets[dir]; y += yoffsets[dir]; } }; struct Doorway { Location location; int direction; Doorway (Location loc, int dir): location(loc), direction(dir) {} bool operator< (const Doorway& d) const {return (location < d.location) || (location == d.location && direction < d.direction); } }; int main () { // Ball of string solution // // From any location (X,Y), try to go N, E, S, W in turn, but // never passing through the same doorway twice. As we go, we trail // a "string" that we can use to back up if we get blocked. // vector thread; // records directions we have moved in set passedThru; // what have we tried already? Location loc = Location(0,0); bool done = false; while (!done) { string walls = readWalls(); int dir = -1; for (int d = 0; d < 4 && dir < 0; ++d) { if (walls[d] != 'X' && passedThru.count(Doorway(loc,d)) == 0) { dir = d; } } if (dir >= 0) { // move forward thread.push_back(dir); passedThru.insert (Doorway(loc, dir)); loc.move(dir); passedThru.insert (Doorway(loc, (dir + 2) % 4)); cout << directions[dir] << endl; done = walls[dir] == 'O'; } else { dir = thread.back(); thread.pop_back(); dir = (dir + 2) % 4; loc.move(dir); cout << directions[dir] << endl; } } cerr << "Done!" << endl; readWalls(); return 0; }