I\'m trying to write a program that can traverse a maze using a graph (Which I t
ID: 3625493 • Letter: I
Question
I'm trying to write a program that can traverse a maze using a graph (Which I think needs to be stored as an array) such as this one (Where the "P" reprents people, and where the "X" represents the location they're trying to reach):
########
# P#
# ## ###
# #
# ### ##
# # X#
########
I think my graph will need to have 4 "edges" or "links" (Left, Right, Top, Bottom) in between each of the "vertices", but I'm not really sure how to get started with that... I also think that to accomplish the search I'll need to do a depth-first search of the graph. Finally, I want to output the correct path (even if it is just cordances for each move to take along the graph).
At this point, I'm just totally lost and I need help.
Explanation / Answer
Dear... // Maze Traversal using recursive techniques: #include "iostream.h"#include "stdlib.h"
void Traverse( char[][7], int, int, int); void Maze(const char[][7]); bool validmove(const char[][7],int,int); bool Edge (int,int); enum direction {DOWN,RIGHT,UP,LEFT}; const int x = 2; const int y = 0; int main() { char maze[8][7] ={{'#','#','#','#','#','#','#','#'}, {'#',' ',' ',' ',' ',' ','P','#'}, {'#',' ','#','#',' ','#','#','#'}, {'#',' ',' ',' ',' ',' ',' ','#'}, {'#',' ','#','#','#',' ','#','#'}, {'#',' ','#',' ',' ',' ','X','#'}, {'#','#','#','#','#','#','#','#'}}; Traverse(maze,x,y,RIGHT); return 0; } void Traverse(char maze[][7], int xlocation, int ylocation, int direction) { maze[xlocation][ylocation]='x'; Maze(maze); if (Edge(xlocation,ylocation)&&xlocation!=x&&ylocation!=y) { cout<<" Phew i got out !!!! I Know the righteous Way"; return; } else if (xlocation==x&&ylocation==x) { cout<<" Back to Square one !!!!"<<endl; return; } else { for (int move =direction,count=0;count<4;count++,move++,move%=4) switch (move) { case DOWN: if (validmove(maze,xlocation+1,ylocation)) { Traverse(maze,xlocation+1,ylocation,LEFT); return; } break; case RIGHT: if (validmove(maze,xlocation,ylocation+1)) { Traverse(maze,xlocation,ylocation+1,DOWN); return; } break; case UP: if (validmove(maze,xlocation-1,ylocation)) { Traverse(maze,xlocation-1,ylocation,RIGHT); return; } break; case LEFT: if (validmove(maze,xlocation,ylocation-1)) { Traverse(maze,xlocation,ylocation-1,UP); return; } break; } } } bool validmove(const char maze[][7],int r, int c) { return (r>=0&&r<=7&&c>=0&&c<=7&&maze[r][c]!='#'); } bool Edge(int x,int y) { if ((x==0||x==7)&&(y>=0&&y<=7)) return true; else if ((y==0||y==6)&&(x>=0&&x<=6)) return true; else return false; } void Maze(const char maze[][7]) { for (int x=0; x<8; x++) { for (int y=0;y<7;y++) cout<<maze[x][y]<<' '; cout<<' '; } cout<<"Press "; cin.get(); }