|
/* Question 4: Maze Problem (Bonus) |
|
* Starting point is m[0][0], need to find a path go to m[9][9]. 0 means OK, |
|
* 1 means cannot go there, boundary is 0 and 9, cannot go beyond boundary. |
|
* Each step can be made horizontally or vertically for one more grid (diagonal |
|
* jump is not allowed). |
|
* Your program should print a series of grid coordinates that start from m[0][0] |
|
* and go to m[9][9] |
|
* Hint: No need to find the shortest path, only need to find one path that gets |
|
* you to desitination. |
|
*/ |
|
|
|
const int DOWN = 0; |
|
const int UP = 1; |
|
const int LEFT = 2; |
|
const int RIGHT = 3; |
|
|
|
// Prints a path to the bottom right corner of the map described by m. |
|
void maze() { |
|
int x = 0; |
|
int y = 0; |
|
int last_move = RIGHT; |
|
int m[10][10] |
|
{ 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, |
|
0, 1, 0, 0, 0, 0, 1, 1, 1, 1, |
|
0, 1, 0, 0, 1, 0, 1, 1, 1, 1, |
|
0, 0, 0, 1, 1, 0, 1, 1, 1, 1, |
|
0, 1, 1, 1, 0, 0, 1, 0, 0, 1, |
|
1, 1, 1, 1, 0, 1, 1, 0, 0, 1, |
|
1, 1, 0, 1, 0, 0, 0, 0, 0, 1, |
|
1, 1, 0, 0, 1, 1, 1, 1, 0, 1, |
|
0, 1, 1, 0, 1, 1, 1, 1, 0, 1, |
|
0, 1, 1, 1, 1, 1, 1, 1, 0, 0 |
|
}; |
|
std::cout << "(row: " << 0 << ", column: " << 0 << ")\n"; |
|
|
|
while ((x != 9) && (y != 9)) { |
|
|
|
// Check move right. |
|
if ((m[y][x+1] == 0) && (last_move != LEFT)) { |
|
x++; |
|
last_move = RIGHT; |
|
} // Check move down. |
|
else if ((m[y+1][x] == 0) && (last_move != UP)) { |
|
y++; |
|
last_move = DOWN; |
|
} // Check move up. |
|
else if ((m[y-1][x] == 0) && (last_move != DOWN)) { |
|
y--; |
|
last_move = UP; |
|
} else { // Move left as last resort. |
|
x--; |
|
last_move = LEFT; |
|
} |
|
std::cout << "(row: " << y << ", column: " << x << ")\n"; |
|
} |
|
std::cout << "(row: " << 9 << ", column: " << 9 << ")\n"; |
|
|
|
} |
|
|
|
int main() { |
|
maze(); |
|
} |
