fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int n,m;
  7.     cin>>n>>m;
  8.      int a[n][m];
  9.      int recentRow[n][m] , recentCol[n][m];
  10.      int dp[n][m];
  11.     for(int i=0;i<n;i++)
  12.     {
  13.         string s;
  14.         cin>>s;
  15.         int x = 0;
  16.         for(int j=0;j<m;j++)
  17.         {
  18.             a[i][j] = (s[x++]-'0');
  19.             recentRow[i][j]=-1;
  20.             recentCol[i][j]=-1;
  21.             dp[i][j]=0;
  22.         }
  23.     }
  24.  
  25.  
  26.  
  27.     for(int i=1;i<n;i++)
  28.     {
  29.         for(int j=1;j<m;j++)
  30.         {
  31.             recentRow[i][j] = ((a[i][j-1]==0) ? j-1 : recentRow[i][j-1]);
  32.             recentCol[i][j] = ((a[i-1][j]==0) ? i-1 : recentCol[i-1][j]);
  33.         }
  34.     }
  35.  
  36.     for(int i=0;i<m;i++)
  37.     {
  38.         if(a[0][i]==0)
  39.             dp[0][i] = 1;
  40.         else
  41.             dp[0][i] = 0;
  42.     }
  43.  
  44.     // for(int i=0;i<n;i++)
  45.     // {
  46.     //     for(int j=0;j<m;j++)
  47.     //     {           
  48.     //         cout<<dp[i][j]<<" ";
  49.     //     }
  50.     //     cout<<endl;
  51.     // }
  52.  
  53.     for(int i=0;i<n;i++)
  54.     {
  55.          if(a[i][0]==0)
  56.             dp[i][0]=1;
  57.         else
  58.             dp[i][0]=0;
  59.     }
  60.  
  61.     // for(int i=0;i<n;i++)
  62.     // {
  63.     //     for(int j=0;j<m;j++)
  64.     //     {           
  65.     //         cout<<dp[i][j]<<" ";
  66.     //     }
  67.     //     cout<<endl;
  68.     // }
  69.  
  70.     for(int i=1;i<n;i++)
  71.     {
  72.         for(int j=1;j<m;j++)
  73.         {
  74.             if(a[i][j]==0){
  75.                 if(recentRow[i][j]!=-1)
  76.                     dp[i][j]= (dp[i][j]%1000000007 + dp[i][recentRow[i][j]]%1000000007)%1000000007;
  77.                 if(recentCol[i][j]!=-1)
  78.                     dp[i][j]= (dp[i][j]%1000000007 + dp[recentCol[i][j]][j]%1000000007)%1000000007;
  79.             }
  80.         }
  81.     }
  82.     if(a[n-1][m-1]!=1 and a[0][0]!=-1)
  83.         cout<<dp[n-1][m-1]<<endl;
  84.     else 
  85.         cout<<0<<endl;
  86.  
  87.  
  88.  
  89. }
  90.  
Success #stdin #stdout 0s 5548KB
comments (?)
stdin
copy 
3 3
000
011
000
stdout
copy 
3
https://ideone.com/4hU83P
language:
C++14 (gcc 8.3)
created:
2 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!