Matrix Path

Using backtracking ...

#include <iostream>
#include <iomanip>
#include <utility>
#include <stack>
#include <vector>
#include <map>
#include <conio.h>

#define MAX_SIZE 4

/*
Given a 2D matrix which contains 0s and 1s. Given two points of matrix whose value is 1. 
Find the path(with only 1s) between the given points

can be done with back tracking
- start from the initial node
- choose all the eligible nodes, return FALSE if None
- go to any one node and recurse from here.
- on failure back track and continue with other nodes
*/

typedef std::pair<int, int> Position; // row, col
std::map<Position, bool> explored;

int A[4][4] = 
    {
        {0, 1, 1, 0}, 
        {1, 0, 1, 0},
        {0, 1, 1, 1},
        {1, 0, 0, 1}
    };

/*
Finds the path of all 1s between start position and end position

- get all the eligible nodes
- add current start node to newPath 
- for every node in eligible nodes, call findPath with start node as current node
- return 1 if we have reached the destination 
- return 0 if the list is exhausted or we are at dead end
*/
bool findPath(Position start, Position end, std::vector<Position>& path)
{
    std::vector<Position> newPath = path;
    std::stack<Position> eligible;
    int x = start.first;
    int y = start.second;
    
    explored[start] = true;
    
    // right
    int p = y+1;
    if(p < MAX_SIZE && A[x][p]) 
    {
        Position t(x, p);
        if(!explored[t])
            eligible.push(t);
    }
    // left
    p = y-1;
    if(p >= 0 && A[x][p]) 
    {
        Position t(x, p);
        if(!explored[t])
            eligible.push(t);
    }
    
    // top
    p = x-1;
    if(p >= 0 && A[p][y]) 
    {
        Position t(p, y);
        if(!explored[t])
            eligible.push(t);
    }
    // bottom
    p = x+1;
    if(p < MAX_SIZE && A[p][y]) 
    {
        Position t(p, y);
        if(!explored[t])
            eligible.push(t);
    }
    
    if(eligible.size() == 0)
        return false; // dead end
    
    newPath.push_back(start);
    
    // recurse
    while(eligible.size() > 0)
    {
        Position tmp = eligible.top();
        eligible.pop();
        
        if(tmp == end) 
        {
            newPath.push_back(tmp);
            path = newPath;
            return true;
        }
        
        if(findPath(tmp, end, newPath))
        {
            // found the path ! 
            path = newPath;
            return true;
        }
        // back track !
    }
    
    return false;
}

int main()
{
    std::vector<Position> path;
    findPath(Position(0,1), Position(3, 0), path);

    if(path.size() == 0)
        std::cout << " no path found !!" << std::endl;
    else
    {
        for(int i = 0; i < path.size(); i++)
            std::cout << path[i].first << path[i].second << std::endl;
    }
    
    getch();
}