Pastie Support Pastie or read my Pastie << self blog

Language: ActionScript C/C++ CSS Diff HTML (ERB / Rails) HTML / XML Java Javascript Objective C/C++ Pascal Perl PHP Plain text Python Ruby Ruby (on Rails) Shell Script (Bash) SQL YAML  

## mark a section (Learn more)

This paste will be private.

#include <stack> #include <iostream> #include <iomanip> #include <string> #include <cassert> // useful assert macro for correctness using namespace std; class Maze{ // Data members - private- not accessible outside private: int rows, cols; bool** Vwall; bool** Hwall; // 2-d array for interior walls bool ** Visited; // flag for each cell public: //constructor- read in Maze data & initialize Maze(){ int num; cin >> rows; cin >> cols; Vwall = new bool * [rows]; // rows x cols-1 is size Hwall = new bool * [rows-1]; // (rows-1) x cols is size Visited = new bool * [rows]; // rows x cols for( int i = 0 ; i < rows ; i++ ) {Vwall[i] = new bool[cols-1]; Visited[i] = new bool[cols]; if (i < (rows-1)) Hwall[i] = new bool[cols];} for(int i = 0; i < rows ; i++){ // read in wall data for(int j = 0; j < (cols-1); j++){ // Vertical wall data cin >> num; if (num == 0) Vwall[i][j] = false; else Vwall[i][j] = true;} if (i < (rows-1)) // Horizontal walls data for(int j = 0; j < cols; j++){ cin >> num; if (num == 0) Hwall[i][j] = false; else Hwall[i][j] = true;} for (int j=0; j < cols; j++) Visited[i][j] = false;} // All free } // destructor to free up the Vwall, Hwall space ~Maze(){ for( int i = 0 ; i < rows ; i++ ) {delete [] Vwall[i]; delete [] Visited[i];} for( int i = 0 ; i < (rows-1) ; i++ ) {delete [] Hwall[i];} delete [] Vwall; delete [] Hwall; delete [] Visited; } void showmaze(){ for (int i = 0; i < cols; i++) {cout << " ..";} cout << endl; // draw top border for (int i = 0; i < rows; i++) { cout << ":" ; // left outer wall for (int j = 0; j < (cols - 1); j++) {cout << " "; if (Vwall[i][j]) cout << ":" ; else cout << " ";} cout << " :" << endl; // right outer wall if (i < (rows - 1)) {for (int j = 0; j < cols; j++) {if (Hwall[i][j]) cout << " .." ; else cout << " ";}} else {for (int j = 0; j < cols; j++) cout << " ..";} cout << endl;} } bool canmove(int x, int y, int dir){ switch(dir){ case 1: // move up {return ((x > 0) && !Hwall[x-1][y] && !Visited[x-1][y]);} case 2: // move right {return ((y < cols - 1) && !Vwall[x][y] && !Visited[x][y+1]);} case 3: // move down {return ((x < rows - 1) && !Hwall[x][y] && !Visited[x+1][y]);} case 4: // move left {return ((y > 0) && !Vwall[x][y-1] && !Visited[x][y-1]);} }} void solve(int x1, int y1, int x2, int y2){ assert ((x1 <= rows - 1) && (y1 <= cols - 1)); // Sanity check assert ((x2 <= rows - 1) && (y2 <= cols - 1)); // for Rat & Cheese // showmaze(); stack<int> Stck; int curX = x1; int curY = y1; int dir = 1; bool flag = false; do{ while (dir < 4) { if ((curX == x2) && (curY == y2)) {flag = true;break;}; if (canmove(curX,curY,dir)) { Visited[curX][curY] = true; Stck.push(curX); Stck.push(curY); Stck.push(dir); // cout << "Move from " << curX << "," << curY << " dir " << dir; switch(dir){ case 1: {curX = curX - 1; break;} case 2: {curY = curY + 1; break;} case 3: {curX = curX + 1; break;} case 4: {curY = curY - 1;}} dir = 1; // cout << " to " << curX << "," << curY << endl; } else dir++;} if (flag || Stck.empty()) break; else { dir = Stck.top() + 1; Stck.pop(); curY = Stck.top(); Stck.pop(); curX = Stck.top(); Stck.pop(); }} while (true); if (flag) {while (!Stck.empty()){ cout << setw(1) << Stck.top(); Stck.pop(); Stck.pop(); Stck.pop();} cout << endl;} else {cout << "0" << endl;} // no path exists } };