fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6.  
  7. #define all(x) x.begin(),x.end()
  8. #define v(x) vector<x>
  9. #define nl '\n'
  10. ll mod = 1e9+7;
  11. int h;
  12. vector<vector<char>> grid(1001,vector<char> (1001));
  13. vector<vector<ll>> dp(1001,vector<ll> (1001,-1));
  14.  
  15. ll CountWays(ll r , ll c)
  16. {
  17.     // base
  18.     if(r > h-1 or c > h-1 or grid[r][c] == '*') return 0;
  19.     if(r == h-1 and c == h-1) return 1;
  20.  
  21.     // dp
  22.     if(dp[r][c] != -1) return dp[r][c];
  23.  
  24.  
  25.     return dp[r][c] = (CountWays(r+1,c)%mod + CountWays(r,c+1)%mod)%mod;
  26. }
  27.  
  28.  
  29. int main()
  30. {
  31.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  32.     cin >> h;
  33.     for (int i = 0; i < h; i++)
  34.     {
  35.         for (int j = 0; j < h; j++)
  36.         {
  37.             cin >> grid[i][j];
  38.         }
  39.  
  40.     }
  41.  
  42.     cout << CountWays(0,0);
  43. }
Success #stdin #stdout 0.01s 12492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FQ8mLR
language:
C++14 (gcc 8.3)
created:
3 days 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!