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;
    }
}
Comments