fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define m 20011
  3. using namespace std;
  4. long long int a[301][301];
  5. long long int dp[301][301][2][301];
  6. int r,c,d;
  7. long long solve(int x,int y,int dleft,int rleft){
  8.  
  9.     if(x==r && y==c)
  10.         return 1;
  11.     if(a[x][y]==0)
  12.         return 0;
  13.     if(dp[x][y][0][dleft]!=-1){
  14.         if(dp[x][y][1][rleft]!=-1)
  15.             return dp[x][y][1][rleft]+dp[x][y][0][dleft];
  16.         else
  17.             return dp[x][y][0][dleft];
  18.     }else if(dp[x][y][1][rleft]!=-1)
  19.         return dp[x][y][1][rleft];
  20.  
  21.  
  22.     if(dleft>0 && x<r){
  23.         dp[x][y][0][dleft]=solve(x+1,y,dleft-1,d)%m;
  24.  
  25.     }else
  26.         dp[x][y][0][dleft]=0;
  27.  
  28.     if(rleft>0 && y<c){
  29.         dp[x][y][1][rleft]=solve(x,y+1,d,rleft-1)%m;
  30.     }else
  31.     dp[x][y][1][rleft]=0;
  32.  
  33.  
  34.     return dp[x][y][0][dleft]+dp[x][y][1][rleft];
  35. }
  36. int main(){
  37.  
  38.  
  39.     cin>>r>>c>>d;
  40.     a[1][1]=1;
  41.     a[r][c]=1;
  42.     int i,j;
  43.     for(i=1;i<=r;++i){
  44.         for(j=1;j<=c;++j)
  45.             cin>>a[i][j];
  46.     }
  47.     memset(dp,-1,sizeof(dp));
  48.     dp[1][1][1][d]=0;
  49.     dp[1][1][0][d]=0;
  50.     if(r>1){
  51.         dp[1][1][0][d]=solve(2,1,d-1,d)%m;
  52.     }
  53.     if(c>1){
  54.         dp[1][1][1][d]=solve(1,2,d,d-1)%m;
  55.     }
  56.     if(r==1 && c==1){
  57.         cout<<1;
  58.  
  59.     }else
  60.  
  61. cout<<(dp[1][1][1][d]+dp[1][1][0][d])%m;
  62. return 0;
  63. }
Success #stdin #stdout 0.1s 442880KB
comments (?)
stdin
copy 
3 4 2
1 1 1 1
0 1 1 1
1 1 1 1
stdout
copy 
5
https://ideone.com/GWwTzf
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!