Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <utility>
- #define pb push_back
- #define mp make_pair
- using namespace std;
- long long dp[310][310][310][2];
- int main()
- {
- int r,c,d;
- bool is[310][310];
- cin>> r>> c>> d;
- for( int i= 0; i < r; i++ )
- {
- for( int j= 0; j< c; j++ )
- cin >> is[i][j];
- }
- for( int i= 0; i< r; i++ )
- {
- for( int j= 0; j< c; j++ )
- {
- for(int k = 0; k<=d; k++ )
- {
- dp[i][j][k][0] = dp[i][j][k][1] = 0;
- }
- }
- }
- dp[0][0][0][0] = dp[0][0][0][1] = 1;
- for( int i = 0; i < r; i++ )
- {
- for( int j = 0; j < c; j++ )
- {
- if( i == j && i == 0 ) continue;
- if( is[i][j]== false ) continue;
- for( int k = 1; k <=d; k++ )
- {
- if( i == 0 )
- dp[i][j][k][0] = dp[i][j-1][k-1][0];
- else if( j == 0 )
- dp[i][j][k][1] = dp[i-1][j][k-1][1];
- else
- {
- dp[i][j][k][0] = dp[i][j-1][k-1][0] + dp[i][j-1][k][1];
- dp[i][j][k][1] = dp[i-1][j][k-1][1] + dp[i-1][j][k][0];
- }
- }
- }
- }
- cout << endl;
- long long sum= 0;
- for( int i = 0; i <= d; i++)
- sum += dp[r-1][c-1][i][0] + dp[r-1][c-1][i][1];
- for( int i = 0; i <r; i++ )
- {
- for( int j = 0; j < c; j++ )
- {
- int temp = 0;
- for( int k = 0; k <=d;k++ )
- temp +=dp[i][j][k][0] + dp[i][j][k][1];
- cout << temp << " ";
- }
- cout << endl;
- }
- cout << sum << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement