Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <utility>
  5.  
  6. #define pb push_back
  7. #define mp make_pair
  8.  
  9. using namespace std;
  10.  
  11.  
  12. long long dp[310][310][310][2];
  13.  
  14. int main()
  15. {
  16. int r,c,d;
  17. bool is[310][310];
  18. cin>> r>> c>> d;
  19. for( int i= 0; i < r; i++ )
  20. {
  21. for( int j= 0; j< c; j++ )
  22. cin >> is[i][j];
  23. }
  24.  
  25. for( int i= 0; i< r; i++ )
  26. {
  27. for( int j= 0; j< c; j++ )
  28. {
  29. for(int k = 0; k<=d; k++ )
  30. {
  31. dp[i][j][k][0] = dp[i][j][k][1] = 0;
  32. }
  33. }
  34. }
  35. dp[0][0][0][0] = dp[0][0][0][1] = 1;
  36.  
  37. for( int i = 0; i < r; i++ )
  38. {
  39. for( int j = 0; j < c; j++ )
  40. {
  41. if( i == j && i == 0 ) continue;
  42. if( is[i][j]== false ) continue;
  43. for( int k = 1; k <=d; k++ )
  44. {
  45. if( i == 0 )
  46. dp[i][j][k][0] = dp[i][j-1][k-1][0];
  47. else if( j == 0 )
  48. dp[i][j][k][1] = dp[i-1][j][k-1][1];
  49. else
  50. {
  51. dp[i][j][k][0] = dp[i][j-1][k-1][0] + dp[i][j-1][k][1];
  52. dp[i][j][k][1] = dp[i-1][j][k-1][1] + dp[i-1][j][k][0];
  53. }
  54. }
  55. }
  56. }
  57. cout << endl;
  58. long long sum= 0;
  59. for( int i = 0; i <= d; i++)
  60. sum += dp[r-1][c-1][i][0] + dp[r-1][c-1][i][1];
  61.  
  62. for( int i = 0; i <r; i++ )
  63. {
  64. for( int j = 0; j < c; j++ )
  65. {
  66. int temp = 0;
  67. for( int k = 0; k <=d;k++ )
  68. temp +=dp[i][j][k][0] + dp[i][j][k][1];
  69. cout << temp << " ";
  70. }
  71. cout << endl;
  72.  
  73. }
  74.  
  75.  
  76.  
  77. cout << sum << endl;
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement