Guest User

Untitled

a guest
Nov 19th, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  5. #define MOD 20011
  6.  
  7. int main() {
  8.  
  9.     fastio;
  10.  
  11.     ll n,m,d;
  12.     vector<vector<char>> grid(305,vector<char>(305));
  13.     vector<vector<ll>> dp(305 , vector<ll>(305));
  14.  
  15.     cin >> n >> m >> d;
  16.     ll h = d+1,k = d+1;
  17.     for(ll i = 0; i < n ;i++){
  18.         for(ll j = 0; j < m; j++){
  19.             cin >> grid[i][j];
  20.         }
  21.     }
  22.  
  23.     // OPTIMAL SUB-PROBLEM :
  24.  
  25.     // dp[i][j] = number of ways one can reach cell(i,j) obeying the given rules :D
  26.  
  27.     // BASE CASE :
  28.  
  29.     dp[0][0] = 1;
  30.  
  31.     for(ll i = 1; i <= d; i++){
  32.         if(grid[i][0] == '0'){
  33.             h = i;
  34.             break;
  35.         }
  36.         else dp[i][0] = 1;
  37.     }
  38.  
  39.     for(ll j = 1; j <= d; j++){
  40.         if(grid[0][j] == '0'){
  41.             k = j;
  42.             break;
  43.         }
  44.         else dp[0][j] = 1;
  45.     }
  46.  
  47.     for(ll i = h; i < n; i++) dp[i][0] = 0;
  48.     for(ll j = k; j < m; j++) dp[0][j] = 0;
  49.  
  50.     // RECURSIVE RELATION :
  51.  
  52.     for(ll i = 1; i < n; i++){
  53.         for(ll j = 1; j < m; j++){
  54.  
  55.             if(grid[i][j] == '0') dp[i][j] = 0;
  56.  
  57.             else if(i - d - 1 >= 0 && j - d - 1>= 0) dp[i][j] = (max(dp[i-1][j] + dp[i][j-1] - dp[i-d-1][j] - dp[i][j-d-1] , ll(0)))%MOD;
  58.             else if(i - d - 1 < 0 && j - d - 1 < 0) dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
  59.             else if(i - d - 1 >= 0 && j - d - 1 < 0) dp[i][j] = (max(dp[i-1][j] + dp[i][j-1] - dp[i-d-1][j] , ll(0)))%MOD;
  60.             else if(i - d - 1 < 0 && j - d - 1 >= 0) dp[i][j] = (max(dp[i-1][j] + dp[i][j-1] - dp[i][j-d-1] , ll(0)))%MOD;
  61.         }
  62.     }
  63.  
  64.     // OPTIMAL SOLUTION :
  65.  
  66.     cout << (dp[n-1][m-1])%MOD;
  67.  
  68.     return 0;
  69. }
Add Comment
Please, Sign In to add comment