EE205 Project 1
Assign 2019-04-04 Due 2018-04-30
Rat in a Maze
A Maze is given as M*N binary matrix of blocks and there is a rat initially at (0, 0) ie. maze[0][0] and the rat wants to eat food which is present at some given block in the maze (fx, fy). In a maze matrix, 0 means that the block is a dead end and 1 means that the block can be used in the path from source to destination. The rat can move in any direction (not diagonally) to any block provided the block is not a dead end.
The task is to check if there exists any path so that the rat can reach the food or not. It is not needed to print the path.
Example:
Input : maze[4][5] = {
{1, 0, 1, 1, 0}, {1, 1, 1, 0, 1}, {0, 1, 0, 1, 1}, {1, 1, 1, 1, 1}
}
fx = 2, fy=3 Output : Path Found!
Thepathcanbe:(0,0)->(1,0)->(1,1)->(2,1)->(3,1)->(3,2) ->(3,3)->(2,3)
Structure Used:
1. X : x coordinate of the node
2. Y : y coordinate of the node
3. dir : This variable will be used to tell which all directions we have tried and
which to choose next. We will try all the directions in anti-clockwise manner starting from Up. Initially it will be assigned 0.
o If dir=0 try Up direction.
o If dir=1 try left direction.
o If dir=2 try down direction. o If dir=3 try right direction.
Solution algorithm:
1. Initialize a blank chessboard as M*N matrix. The matrix must be allocated dynamically .
2. We will push a node with indexes i=0, j=0 and dir=0 into the stack.
3. Move to all the direction of the topmost node one by one in an anti-clockwise manner and each time as we try out a new path we will push that node (block of the
maze) in the stack.
4. We will increase dir variable of the topmost node each time so that we can try a new
direction each time unless all the directions are explored ie. dir=4.
5. If dir equals to 4 we will pop that node from the stack that means we are retracting
one step back to the path where we came from.
6. We will also maintain a visited matrix which will maintain which blocks of the
maze are already used in the path or in other words present in the stack. While trying out any direction we will also check if the block of the maze is not a dead end and is not out of the maze too.
7. We will do this while either the topmost node coordinates become equal to the food¡¯s coordinates that means we have reached the food or the stack becomes empty which means that there is no possible path to reach the food.
Submit:
1. Files to submit: EE205_studentID_name(CN).h and EE205_studentID_name(CN).cpp
2. The following class definition is included in your header file. You should complete the methods of the class in the .cpp file. Some comments could be added to be read easily by TA
#ifndef maze_EE_h
#define maze_EE_h
#include
#include
#include
using namespace std;
class node { public:
int x, y; int dir;
node(int i, int j) {
x = i; y = j;
// Initially direction // set to 0
dir = 0;
} };
class RatInMaze{ private:
int fx, fy; bool **visited; int **maze;
int m,n; stack
public:
void get_maze(int **mz,int m, int n); void get_food_coordinate(int X, int Y); bool isReachable();
void print_visited();
// Food coordinates
};
#endif /* maze_EE_h */
3. The description of the class node and RatInMaze as followed:
a) The node class is used to store a block of the maze. The variable x and y
denote the coordinate of the block. And the dir denotes the directions we will try.
If dir=0 try Up direction.
If dir=1 try left direction. If dir=2 try down direction. If dir=3 try right direction.
b) In class RatInMaze, the variable fx and fy are used to store the coordinates of food. The coordinates can be obtained by method ¡°void get_food_coordinate(int X, int Y)¡±.
c) The visited matrix which will maintain which blocks of the maze are already used in the path.
d) The maze is a M*N binary matrix. In a maze matrix, 0 means that the block is a dead end and 1 means that the block can be used in the path from source to destination.
e) The maze matrix is obtained by the method ¡°void get_maze(int **mz,int m, int n);¡±. In the method, the visited matrix can also be initialization.
f) The method ¡°bool isReachable();¡± is to check if there exists any path so that the rat can reach the food or not.
g) The method ¡°void print_visited();¡± is to print the visited matrix.
If necessary, you can add any variable or methods into the class. 4. Score
a) The maze and visited M*N matrices should be dynamically generated. (30%) CAUTION: If the matrix is a static 2-D array, the score will be marked 0 !
b) The method ¡°bool isReachable();¡± is correct to judge if the path exists or not.(60%)
c) The method ¡°void print_visited();¡± can print the visited matrix.(10%)
5. Submit by email:
a) Email subject : EE205_studentID_studentName(CN).
b) Send email to TA after attaching your .h and .cpp files.
c) TA¡¯s (Xiao Zhuqi) email address: zqxiao.shawn@qq.com
6. Due date: Due 2018-04-30
a) No acceptance after 5 days.
b) 10% penalty per day up to 5 days.
7. The following file can be used to test your code.
1. int main()
2. {
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
RatInMaze a,b;
// The first Maze matrix int maze1[4][5] = {
{ 1, 0, 1, 1, 0 }, { 1, 1, 1, 0, 1 }, { 0, 1, 0, 1, 1 }, { 1, 1, 1, 1, 1 }
};
int **mz = new int* [4]; for (int i=0; i<5; i++) {
mz[i] = new int[5]; }
for (int i=0; i<4; i++) { for (int j=0; j<5; j++) {
mz[i][j] = maze1[i][j];
}
}
// Food coordinates
intfx=2;
intfy=3; a.get_food_coordinate(fx, fy); a.get_maze(mz, 4, 5);
26.
27. if (a.isReachable()) {
28. cout << "Path Found!" << '\n';
29. 30.
31. }
32. else
33. cout << "No Path Found!" << '\n';
34.
35. a.print_visited(); 36.
37. // The second Maze matrix
38. int maze2[5][6] = {
39. {1,0,1,1,0, 1},
40. {1,1,0,0,1, 1},
41. {0,1,0,1,1, 0},
42. {1,1,1,0,1, 0},
43. {1,0,1,0,1, 0},
44. };
45.
46. mz = new int* [5];
47. for (int i=0; i<5; i++) {
48. mz[i] = new int[6];
49. }
50. for (int i=0; i<5 i++) {
51. for (int j=0; j<6; j++) {
52. mz[i][j] = maze2[i][j];
53. }
54. }
55.
56. // Food coordinates
57. fx=3;
58. fy=4;
59. b.get_food_coordinate(fx, fy);
60. b.get_maze(mz, 5, 6);
61.
62. if (b.isReachable()) {
63. cout << "Path Found!" << '\n';
64. 65.
66. }
67. else
68. cout << "No Path Found!" << '\n';
69.
70. b.print_visited();
71. return 0;
72. }