vivek_ragi

printallPathsfromMatrix

Jun 2nd, 2021
667
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. bool isSafe(vector< vector<int> > &mat, int i, int j)
  6. {
  7.  
  8.     if(mat[i][j] == -1 or i < 0 or j < 0)
  9.     return false;
  10.  
  11.     return true;
  12. }
  13.  
  14.  
  15. bool solve(vector< vector<int> > mat, int row, int col, map<pair<int,int>, bool> &cache, vector<pair<int,int> > ans)
  16. {
  17.     cout << "Entering :" << "\n";
  18.     if(!isSafe(mat,row,col))
  19.     {
  20.         return false;
  21.     }
  22.  
  23.     pair<int,int> point;
  24.     point.first = row;
  25.     point.second = col;
  26.  
  27.     if(cache.find(point) != cache.end()) //already present in cache
  28.     {
  29.         return cache[point];
  30.     }
  31.  
  32.     bool flag = false;
  33.     if((row == 0 and col == 0) or (solve(mat,row - 1, col, cache, ans)) or (solve(mat,row, col - 1, cache, ans)) )
  34.     {
  35.         ans.push_back(point); // will have the path
  36.         flag = true;
  37.     }
  38.  
  39.     cache[point] = flag;
  40.  
  41.     return flag;
  42. }
  43.  
  44. int main()
  45. {
  46.     int r,c;
  47.     cin >> r >> c;
  48.     vector< vector<int> > mat(r, vector<int> (c,0));
  49.  
  50.     // - 1 means there is block u cant move along that
  51.     for(int i = 0; i < r; ++i)
  52.     {
  53.         for(int j = 0; j < c; ++j)
  54.         {
  55.             cin >> mat[i][j];
  56.         }
  57.     }
  58.  
  59.     cout << "Printting Matrix" << "\n";
  60.    
  61.     for(int i = 0; i < r; ++i)
  62.     {
  63.         for(int j = 0; j < c; ++j)
  64.         {
  65.             cout <<  mat[i][j] << " ";
  66.         }
  67.         cout << "\n";
  68.     }
  69.    
  70.     map< pair<int,int>, bool> cache;
  71.     vector< pair<int,int> > ans;
  72.     // will call solve
  73.  
  74.     if(solve(mat,r - 1, c - 1, cache, ans))
  75.     {
  76.         for(auto x: ans)
  77.         {
  78.             cout << x.first << " " << x.second;
  79.             cout << "\n";
  80.         }
  81.     }
  82. }
RAW Paste Data