vivek_ragi

OUT_OF_BOUNDARY_PATHS

Jun 24th, 2021
1,110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
  4.         // you can do with 3D dp (or) by seeing contraints you can calculate for each move
  5.         vector<vector<int>> dp1(m, vector<int>(n,0));
  6.         int mod = 1000 * 1000 * 1000 + 7;
  7.         int ans= 0;
  8.         dp1[startRow][startColumn] = 1;
  9.         for(int moves = 1; moves <= maxMove; moves++) {
  10.            
  11.             //for every new move we will be swaping and computing the answer
  12.             //we need till k -1
  13.             //1 move for going to the boundary
  14.            
  15.             vector<vector<int>> dp2(m, vector<int>(n,0));
  16.            
  17.             for(int i = 0; i < m ; ++i) {
  18.                 for(int j = 0; j < n; ++j) {
  19.                     // check all directions
  20.                     // form i, j
  21.                    
  22.                     //right
  23.                     dp2[i][j] = (dp2[i][j] + ((j + 1 < n) ? dp1[i][j + 1] : 0)) % mod;
  24.                     //left
  25.                     dp2[i][j] = (dp2[i][j] + ((j - 1 >= 0) ? dp1[i][j - 1] : 0)) % mod;
  26.                    
  27.                     //top
  28.                     dp2[i][j] = (dp2[i][j] + ((i - 1 >= 0) ? dp1[i - 1][j] : 0)) % mod;
  29.                     //bottom
  30.                     dp2[i][j] = (dp2[i][j] + ((i + 1 < m) ? dp1[i + 1][j] : 0)) % mod;
  31.                    
  32.                 }
  33.             }
  34.            
  35.             for(int i = 0; i < m; ++i) {
  36.                 ans = (ans + dp1[i][0]) % mod;;
  37.                 ans = (ans + dp1[i][n - 1]) % mod;
  38.             }
  39.            
  40.             for(int i = 0; i < n; ++i) {
  41.                 ans = (ans + dp1[0][i]) % mod;;
  42.                 ans = (ans + dp1[m - 1][i]) % mod;
  43.             }
  44.             swap(dp1, dp2);
  45.            
  46.         }
  47.        
  48.         return ans;
  49.        
  50.     }
  51. };
RAW Paste Data