Advertisement
sasa2742002

Untitled

Dec 2nd, 2022
726
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. #define T     \
  7.   ll rrr;     \
  8.   cin >> rrr; \
  9.   for (ll w1 = 0; w1 < rrr; w1++)
  10. #define cin(vec, a) for (ll i = 0; i < a && cin >> vec[i]; i++)
  11. #define cout(vec, a) for (ll i = 0; i < a && cout << vec[i] << " "; i++)
  12. #define MOD 1000000007
  13. #define PI 3.14159265
  14. #define ceil(a, b) ((a / b) + (a % b ? 1 : 0))
  15. #define all(v) v.begin(), v.end()
  16. #define rall(v) v.rbegin(), v.rend()
  17. #include <iostream>
  18. #define INF 1e9
  19. #define mod 1000000007
  20. #include <string>
  21. #define el '\n'
  22. #define sp ' '
  23. #define loop(n) for (int i = 0; i < n; i++)
  24. typedef long long ll;
  25. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  26. #define multi_ordered_set tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
  27.  
  28. void sasa()
  29. {
  30.   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  31. #ifndef ONLINE_JUDGE
  32.   freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  33. #endif
  34. }
  35. vector<vector<char>> v;
  36. ll n;
  37. vector<vector<ll>> memo(1005, vector<ll>(1005, -1));
  38. bool isvalid(int i, int j)
  39. {
  40.   if (i < 0 || j < 0 || i >= n || j >= n || v[i][j] == '*')
  41.     return false;
  42.  
  43.   return true;
  44. }
  45. ll grid_path(ll i, ll j, ll n, ll m)
  46. {
  47.   if (i == n - 1 && j == m - 1)
  48.   {
  49.     return 1;
  50.   }
  51.  
  52.   if (memo[i][j] != -1)
  53.     return (memo[i][j] % mod);
  54.  
  55.   ll k = 0;
  56.   if (isvalid(i + 1, j))
  57.   {
  58.     k = (k % mod + grid_path(i + 1, j, n, m) % mod) % mod;
  59.   }
  60.   if (isvalid(i, j + 1))
  61.   {
  62.     k = (k % mod + grid_path(i, j + 1, n, m) % mod) % mod;
  63.   }
  64.   return memo[i][j] = (k % mod);
  65. }
  66. void solve()
  67. {
  68.  
  69.   cin >> n;
  70.   v = vector<vector<char>>(n, vector<char>(n));
  71.   for (ll i = 0; i < n; i++)
  72.   {
  73.     for (ll j = 0; j < n; j++)
  74.     {
  75.       cin >> v[i][j];
  76.     }
  77.   }
  78.   cout << grid_path(0, 0, n, n);
  79. }
  80.  
  81. int main()
  82. {
  83.   sasa();
  84.   ll t = 1, i = 1;
  85.   // cin >> t;
  86.   while (t--)
  87.   {
  88.     //  cout << "Case #" << i << ": ";
  89.     solve();
  90.     i++;
  91.     if (!t)
  92.       break;
  93.     cout << "\n";
  94.   }
  95.  
  96.   return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement