Find path in maze
Given a grid of size X, Y where several grid points are not accessible, find a path from start (0,0) to end (X-1, Y-1) when one can only move "up" or "right"
/*
* FindPathInGrid.cpp
*
* Created on: May 10, 2012
* Author: Kiran Hegde
*/
#include <iostream>
#include <map>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
struct Point {
int x;
int y;
};
/**
* create a grid
*/
void getGrid(bool **grid, int width, int height) {
/*
* generate random numbers between 0 and 4. 0 indicates an obstacle
* There is probability of 1/5 that a point is an obstacle
* All obstacles are marked true in the grid
*/
srand(time(NULL));
for (int i=0; i<width; i++) {
for (int j=0; j<height; j++) {
grid[i][j] = ((rand() % 5 == 0)? true : false );
}
}
}
/**
* rows of matrix represent height (y direction) and
* columns of matrix represent width (x direction)
*/
void printGrid(bool **grid, int width, int height) {
cout << "Bottom Left = (0, 0) Top Right = (" << width-1 << ", "
<< height-1 << ")" << endl;
for (int i=height-1; i>=0; i--) {
for (int j=0; j<width; j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
}
/**
* Path is stored from end to start. So reverse while printing
*/
void printPath(vector<Point> &path) {
for (int i=path.size()-1; i>=0; i--) {
cout << "(" << path[i].x << "," << path[i].y << ") ";
}
}
/*
* A functor object for comparing points
* if points are equal return false or else return true
*/
struct pointComp {
bool operator() (const Point p1, const Point p2) const {
if ((p1.x == p2.x) && (p1.y == p2.y))
return false;
return true;
}
};
/**
* Find a path from 0,0 (start) to X,Y (end) in a grid where one can only move
* up or right and obstacles can be present (i.e. certain positions are not
* allowed)
*/
bool findPath(int x, int y, bool **grid, vector<Point> &path, map<Point, bool, pointComp> &cache) {
Point p;
p.x = x;
p.y = y;
if (cache.find(p) != cache.end()) {
return cache[p];
}
path.push_back(p); //p is a potential point on the path
if (x == 0 && y == 0) {
return true;
}
bool success = false;
if ((x >= 1) && ( ! grid[x-1][y])) {
success = findPath(x-1, y, grid, path, cache);
}
if ((!success) && (y >= 1) && (! grid[x][y-1])) {
success = findPath(x, y-1, grid, path, cache);
}
if (! success) { //p is not a point on path, remove it
path.pop_back();
}
cache[p] = success; //cache this result, so that it can be reused
return success;
}
/**
* Test the code
*/
int main() {
int width = 10;
int height = 10;
bool **grid = new bool* [height];
for (int i=0; i<10; i++) {
grid[i] = new bool[width];
}
getGrid(grid, width, height);
printGrid(grid, width, height);
map<Point, bool, pointComp> cache;
vector<Point> path;
//Find out if a path exists from one corner (0,0) to the other (9,9)
bool success = findPath(width-1, height - 1, grid, path, cache);
if (success) {
cout << "Path: " << endl;
printPath(path);
cout << endl;
}
else {
cout << "No path exists" << endl;
}
}