### 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;`
`    }`
`}`