Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
/* Public domain recursive maze solver by Tyler Kennedy (tk@tkte.ch) */
/* Example maze:
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
W W W W W W
W WWWWWWWWW W WWWWWWWWWWWWWWWWWWWW W W W WWW W
W W W W WWW W W W W W W
W W W WWWWWWWWWWWW W W W WWWWWWWWWW W W
WWWWWW WWWWWWWWWWWWW W W W W W W
W W W WWWWWWWWWWWWWWW W WWWWWWWWWWWWWW W
W WWWWWW W W W W W
W W WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW W W
WWWWWW W W W W W W W W
W W W WWWWWWWWW W WWWWWW W WWWWWWWWWWW WWWWWW W W W
W WWWWWW W W W W WWWWWW W W
W W WWWWWWWWW W WWWWWWWWW WWWWWWWWWWW WWWWWWWWWWWWW W
WSW W W WEW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
*/
/* Example output:
Start of the maze found at <1,13>.
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
W W W W.......W......W
W WWWWWWWWW W WWWWWWWWWWWWWWWWWWWW W W. .W. [url]WWW.W[/url]
W W W W WWW W W W. ... W W.W
W W W WWWWWWWWWWWW W W W.WWWWWWWWWW W.W
WWWWWW WWWWWWWWWWWWW W W W W... W.W
W........W W WWWWWWWWWWWWWWW W.WWWWWWWWWWWWWW.W
W.WWWWWW.W W W..............W.W
W......W.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW.W.W
WWWWWW.W.W...........W ...W W.........W.W.W
W......W.W.WWWWWWWWW.W WWWWWW.W.WWWWWWWWWWW. WWWWWW.W.W.W
W.WWWWWW.W.........W.W .W............. WWWWWW...W.W
W.W .WWWWWWWWW.W.WWWWWWWWW.WWWWWWWWWWW WWWWWWWWWWWWW.W
WSW ...........W........... W WEW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
*/
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#define MAZE_START 'S'
#define MAZE_END 'E'
#define MAZE_WALL 'W'
#define MAZE_SPACE ' '
#define MAZE_PATH '.'
#define MAZE_SKIP '#'
int solve(std::vector<std::string> &maze, int x, int y);
inline int isGood(char t);
int main(int argv,char *argc[]){
std::fstream fin(((argv > 1) ? argc[1] : "C:\\maze.txt"),std::ios::in);
std::vector<std::string> maze;
std::string temp;
int x,y,mX,mY;
std::string::iterator sit;
std::vector<std::string>::iterator vit;
if(!fin.good()){
std::cout << "Couldn't open the file for input." << std::endl;
return 1;
}
while(!fin.fail()){
getline(fin,temp);
if(!fin.fail()){
maze.push_back(temp);
}
}
for(vit = maze.begin(), y = 0; vit < maze.end(); vit++, y++){
for(sit = (*vit).begin(), x = 0; sit < (*vit).end(); sit++, x++){
if(*sit == MAZE_START){
std::cout << "Start of the maze found at <" << x << "," << y << ">." << std::endl;
mX = x;
mY = y;
}
}
}
if(solve(maze,mX,mY)){
for(vit = maze.begin(), y = 0; vit < maze.end(); vit++, y++){
for(sit = (*vit).begin(), x = 0; sit < (*vit).end(); sit++, x++){
if(*sit == MAZE_SKIP){
std::cout << " ";
}else{
std::cout << *sit;
}
}
std::cout << std::endl;
}
}else{
std::cout << "Couldn't solve it." << std::endl;
}
std::cin.get();
return 0;
}
int solve(std::vector<std::string> &maze, int x, int y){
if(x > maze[y].size() || x < 0 || y > maze.size() || y < 0)
return false;
if(maze[y][x] == MAZE_END)
return true;
if(maze[y][x] != MAZE_START)
maze[y][x] = MAZE_PATH;
if(y > 0 && isGood(maze[y-1][x])){
if(solve(maze,x,y-1))
return true;
}
if(x < maze[y].size() - 1 && isGood(maze[y][x+1])){
if(solve(maze,x+1,y))
return true;
}
if(y < maze.size() - 1 && isGood(maze[y+1][x])){
if(solve(maze,x,y+1))
return true;
}
if(x > 0 && isGood(maze[y][x-1])){
if(solve(maze,x-1,y))
return true;
}
maze[y][x] = MAZE_SKIP;
return false;
}
int isGood(char t){
if(t != MAZE_PATH && t != MAZE_SKIP && t != MAZE_WALL){
return true;
}
return false;
}
Edited by TkTech, 19 July 2010 - 06:52 PM.
Replaced highlighted code tags with [code]
Back to top
