Programming Homework Help Logo
  1. Home
  2. Itsy Bitsy Spider

3D Maze Itsy Bitsy Spider Game

MazeSolve.cpp #include #include #include #include using namespace std; #define DOWN 5 #define UP 4 #define WEST 3 #define SOUTH 2 #define EAST 1 #define NORTH 0 #define FOUND 1 struct Node { int x,y,z; // the position of the node (level,row,column) vectorchildren; // the children of that node according to its possible directions from the input }; // This function is responsible in returning the direction charcter according to positions of the parent and child nodes char getDirection(Node* parent,Node*child){ if (parent->x > child->x){ return 'D'; } if (parent->x < child->x){ return 'U'; } if (parent->y > child->y){ return 'N'; } if (parent->y < child->y){ return 'S'; } if (parent->z >child->z){ return 'W'; } return 'E'; } // The recursion search responsible for depth first search to find the correct path for the goal node int DFS_Goal_search(Node***graph,Node*cur,Node*goal,map&vis,vector& moves){ if (cur == goal){ // GOAL found for (int i = 0; ichildren.size(); i++){ if (vis.find(cur->children[i]) == vis.end()){ // not visited before moves.push_back(getDirection(cur,cur->children[i])); // record the move done in the path vis[cur->children[i]]; // mark as visited to not visit again on the same path res = DFS_Goal_search(graph, cur->children[i], goal, vis, moves); if (res == FOUND){ // if found abort the search and don't continue return res; } vis.erase(cur->children[i]); // remove child from visited as this path failed moves.pop_back(); // remove the move from the path } } return 0; } int main(){ int l, r, c,gl,gr,gc,sl,sr,sc; int n; mapvisited; // the map responsible for saving the visited nodes to not visit it again cin>> n; Node *** graphNodes; while (n--){ visited.clear(); cin>> l >> r >> c; graphNodes = new Node**[l]; // initialize the 3d array of the levels for (size_ti = 0; i< l; i++) { graphNodes[i] = new Node*[r]; for (size_t j = 0; j < c; j++) { graphNodes[i][j] = new Node[c]; } } cin>>sl>>sr>>sc; cin>>gl>> gr >>gc; string dir; // read data from input and define each node children according to its possible direction moves for (int i = 0; i< l; i++){ for (int j = 0; j < r; j++){ for (int k = 0; k < c; k++){ graphNodes[i][j][k].x = i; graphNodes[i][j][k].y = j; graphNodes[i][j][k].z = k; cin>>dir; if (dir[NORTH] == '1'){ graphNodes[i][j][k].children.push_back(&graphNodes[i][j - 1][k]); } if (dir[EAST] == '1'){ graphNodes[i][j][k].children.push_back(&graphNodes[i][j][k + 1]); } if (dir[SOUTH] == '1'){ graphNodes[i][j][k].children.push_back(&graphNodes[i][j + 1][k]); } if (dir[WEST] == '1'){ graphNodes[i][j][k].children.push_back(&graphNodes[i][j][k - 1]); } if (dir[UP] == '1'){ graphNodes[i][j][k].children.push_back(&graphNodes[i + 1][j][k]); } if (dir[DOWN] == '1'){ graphNodes[i][j][k].children.push_back(&graphNodes[i - 1][j][k]); } } } } // start searching starting from the start node to the goal node DFS_Goal_search(graphNodes, &graphNodes[sl][sr][sc], &graphNodes[gl][gr][gc], visited, vector()); for (size_ti = 0; i< l; i++) { for (size_t j = 0; j < c; j++) { delete[]graphNodes[i][j]; } delete[]graphNodes[i]; } } return 0; }