SHARE
TWEET

Untitled

a guest Sep 19th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     const int dx[4] = {0, 1, 0, -1};
  4.     const int dy[4] = {-1, 0, 1, 0};
  5.     void dfs(vector<vector<vector<int>>>& grid, int i, int j, int N, int past) {
  6.         if (N == 0) {
  7.             return;
  8.         }
  9.         cout << i << ' ' << j << endl;
  10.        
  11.         grid[i][j][N] += past;
  12.         for (int l = 0; l < 4; l++) {
  13.             int new_i = i + dx[l];
  14.             int new_j = j + dy[l];
  15.            
  16.             if (new_i >= 0 && new_i < grid.size() && new_j >= 0 && new_j < grid[0].size()) {
  17.                 dfs(grid, new_i, new_j, N - 1, grid[i][j][N]);
  18.             }
  19.         }
  20.        
  21.     }
  22.    
  23.     int findPaths(int m, int n, int N, int i, int j) {
  24.         vector<vector<vector<int>>> grid;
  25.         grid.resize(m, vector<vector<int>>(n, vector<int>(N + 1)));
  26.        
  27.         grid[i][j][N] = 1;
  28.        
  29.         dfs(grid, i, j, N, 0);
  30.         int ans = 0;
  31.         const int dev = 1e9 + 7;
  32.         for (int k = 0; k < m; k++) {
  33.             for (int l = 0; l < n; l++) {
  34.                 int sum = 0;
  35.                 for (int y = 1; y <= N; y++) {
  36.                     sum += grid[k][l][y];
  37.                 }
  38.                 cout << sum << ' ';
  39.                 for (int h = 0; h < 4; h++) {
  40.                     int new_k = k + dx[h];
  41.                     int new_l = l + dy[h];
  42.                    
  43.                     if (new_k < 0 || new_k >= m || new_l < 0 || new_l >= n){
  44.                         ans += sum;
  45.                         ans %= dev;
  46.                     }
  47.                 }
  48.             }
  49.             cout << endl;
  50.         }
  51.         return ans;
  52.     }
  53. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top