printallPathsfromMatrix

#include <bits/stdc++.h>
using namespace std;


bool isSafe(vector< vector<int> > &mat, int i, int j)
{

    if(mat[i][j] == -1 or i < 0 or j < 0)
    return false;

    return true;
}


bool solve(vector< vector<int> > mat, int row, int col, map<pair<int,int>, bool> &cache, vector<pair<int,int> > ans)
{
    cout << "Entering :" << "\n";
    if(!isSafe(mat,row,col))
    {
        return false;
    }

    pair<int,int> point;
    point.first = row;
    point.second = col;

    if(cache.find(point) != cache.end()) //already present in cache
    {
        return cache[point];
    }

    bool flag = false;
    if((row == 0 and col == 0) or (solve(mat,row - 1, col, cache, ans)) or (solve(mat,row, col - 1, cache, ans)) )
    {
        ans.push_back(point); // will have the path
        flag = true;
    }

    cache[point] = flag;

    return flag;
}

int main()
{
    int r,c;
    cin >> r >> c;
    vector< vector<int> > mat(r, vector<int> (c,0));

    // - 1 means there is block u cant move along that
    for(int i = 0; i < r; ++i)
    {
        for(int j = 0; j < c; ++j)
        {
            cin >> mat[i][j];
        }
    }

    cout << "Printting Matrix" << "\n";

    for(int i = 0; i < r; ++i)
    {
        for(int j = 0; j < c; ++j)
        {
            cout <<  mat[i][j] << " ";
        }
        cout << "\n";
    }

    map< pair<int,int>, bool> cache;
    vector< pair<int,int> > ans;
    // will call solve

    if(solve(mat,r - 1, c - 1, cache, ans))
    {
        for(auto x: ans)
        {
            cout << x.first << " " << x.second;
            cout << "\n";
        }
    }
}