Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
- #define MOD 20011
- int main() {
- fastio;
- ll n,m,d;
- vector<vector<char>> grid(305,vector<char>(305));
- vector<vector<ll>> dp(305 , vector<ll>(305));
- cin >> n >> m >> d;
- ll h = d+1,k = d+1;
- for(ll i = 0; i < n ;i++){
- for(ll j = 0; j < m; j++){
- cin >> grid[i][j];
- }
- }
- // OPTIMAL SUB-PROBLEM :
- // dp[i][j] = number of ways one can reach cell(i,j) obeying the given rules :D
- // BASE CASE :
- dp[0][0] = 1;
- for(ll i = 1; i <= d; i++){
- if(grid[i][0] == '0'){
- h = i;
- break;
- }
- else dp[i][0] = 1;
- }
- for(ll j = 1; j <= d; j++){
- if(grid[0][j] == '0'){
- k = j;
- break;
- }
- else dp[0][j] = 1;
- }
- for(ll i = h; i < n; i++) dp[i][0] = 0;
- for(ll j = k; j < m; j++) dp[0][j] = 0;
- // RECURSIVE RELATION :
- for(ll i = 1; i < n; i++){
- for(ll j = 1; j < m; j++){
- if(grid[i][j] == '0') dp[i][j] = 0;
- 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;
- else if(i - d - 1 < 0 && j - d - 1 < 0) dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
- 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;
- 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;
- }
- }
- // OPTIMAL SOLUTION :
- cout << (dp[n-1][m-1])%MOD;
- return 0;
- }
Add Comment
Please, Sign In to add comment