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 INF LLONG_MAX
- #define MOD 20011
- int main()
- {
- fastio;
- ll r,c,d,w,y,flag = 0;
- vector<vector<ll>> dpleft(305, vector<ll>(305));
- vector<vector<ll>> dpup(305, vector<ll>(305));
- vector<vector<ll>> blockedornot(305, vector<ll>(305));
- cin >> r >> c >> d;
- for( ll i = 1 ; i <= r ; i++)
- {
- for( ll j = 1; j <= c ; j++)
- {
- cin >> blockedornot[i][j];
- }
- }
- dpleft[1][1] = 1;
- dpup[1][1] = 1;
- if( r== 1 && c == 1)
- {
- cout << 1;
- return 0;
- }
- for( ll i = 2 ; i <= d+1 ; i++)
- {
- if( blockedornot[1][i] == 0 ) break;
- else
- {
- dpleft[1][i] = 1;
- }
- }
- for( ll i = 2 ; i <= d+1 ; i++)
- {
- if( blockedornot[i][1] == 0 ) break;
- else
- {
- dpup[i][1] = 1;
- }
- }
- for( ll i = 2 ; i <= r ; i++)
- {
- for( ll j = 2 ; j <= c ; j++)
- {
- flag = 0;
- if( blockedornot[i][j] == 1)
- {
- dpleft[i][j] = dpleft[i][j-1] + dpup[i][j-1];
- dpleft[i][j] = (dpleft[i][j])%MOD;
- if( j-d-1 >= 1)
- {
- for( ll k = j-d-1 ; k <= j-1 ; k++)
- {
- if( blockedornot[i][k] == 0)
- {
- flag = 1;
- break;
- }
- }
- }
- if( j-d-1 >= 1 && flag != 1)
- {
- y = dpleft[i][j] - dpup[i][j-d-1];
- dpleft[i][j] = y%MOD;
- }
- flag = 0;
- dpup[i][j] = dpleft[i-1][j] + dpup[i-1][j] ;
- dpup[i][j] = (dpup[i][j])%MOD;
- if( i-d-1 >= 1)
- {
- for( ll k = i-d-1 ; k <= i-1 ; k++)
- {
- if( blockedornot[k][j] == 0)
- {
- flag = 1;
- break;
- }
- }
- }
- if( i-d-1 >= 1 && flag != 1)
- {
- y = dpup[i][j] - dpleft[i-d-1][j];
- dpup[i][j] = y%MOD;
- }
- }
- }
- }
- w = (dpleft[r][c] + dpup[r][c])%MOD;
- cout << w << "\n";
- //
- // for( ll i = 1 ; i <= r ; i++)
- // {
- // for( ll j = 1; j <= c ; j++)
- // {
- // cout << dpleft[i][j] << "\t";
- // }
- // cout << "\n";
- // }
- //
- // cout << endl;
- //
- // for( ll i = 1 ; i <= r ; i++)
- // {
- // for( ll j = 1; j <= c ; j++)
- // {
- // cout << dpup[i][j] << "\t";
- // }
- // cout << "\n";
- // }
- return 0;
- }
Add Comment
Please, Sign In to add comment