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 and a[0][0]==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  and a[0][0]==0)
  56.             dp[i][0]=1;
  57.         else
  58.             dp[i][0]=0;
  59.     }
  60.  
  61.  
  62.  
  63.     for(int i=1;i<n;i++)
  64.     {
  65.         for(int j=1;j<m;j++)
  66.         {
  67.             if(a[i][j]==0){
  68.                 if(recentRow[i][j]!=-1)
  69.                     dp[i][j]= (dp[i][j]%1000000007 + dp[i][recentRow[i][j]]%1000000007)%1000000007;
  70.                 if(recentCol[i][j]!=-1)
  71.                     dp[i][j]= (dp[i][j]%1000000007 + dp[recentCol[i][j]][j]%1000000007)%1000000007;
  72.             }
  73.         }
  74.     }
  75.  
  76.     // for(int i=0;i<n;i++)
  77.     // {
  78.     //     for(int j=0;j<m;j++)
  79.     //     {           
  80.     //         cout<<recentCol[i][j]<<" ";
  81.     //     }
  82.     //     cout<<endl;
  83.     // }
  84.  
  85.     // for(int i=0;i<n;i++)
  86.     // {
  87.     //     for(int j=0;j<m;j++)
  88.     //     {           
  89.     //         cout<<recentRow[i][j]<<" ";
  90.     //     }
  91.     //     cout<<endl;
  92.     // }
  93.  
  94.  
  95.     if(a[n-1][m-1]!=1 and a[0][0]!=-1)
  96.         cout<<dp[n-1][m-1]<<endl;
  97.     else 
  98.         cout<<0<<endl;
  99.  
  100.  
  101.  
  102. }
  103.  
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
3 3
000
101
000
stdout
copy 
3
https://ideone.com/7zqZ0S
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!