Untitled
unknown
c_cpp
a year ago
4.8 kB
1
Indexable
Never
#include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace chrono; using namespace __gnu_pbds; #define loop(i,a,b) for(int i=a;i<b;i++) #define range(a) a.begin(),a.end() #define pb(a) push_back(a) #define mp make_pair #define ff first #define ss second #define pqb priority_queue<int> #define pqs priority_queue<int,vi,greater<int> > #define w(x) int x; cin>>x; while(x--) #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++) #define mii map<int, int> #define umii unordered_map<int, int> #define mll map<ll, ll> #define umll unordered_map<ll, ll> #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define si set<int> #define sl set<ll> #define vpii vector<pii> #define vpll vector<pl> #define vvi vector<vi> #define vvl vector<vl> #define MOD 1000000007 //**************************// #define fastinout ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL); #ifndef vk20july #define debug(x) cerr<<#x<<" ";_print(x); cerr<<endl; #else #define debug(x) #endif //**********************// //*********************// typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key void _print(ll t) {cerr << t;} void _print(int t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(lld t) {cerr << t;} void _print(double t) {cerr << t;} void _print(ull t) {cerr << t;} template <class T, class V> void _print(pair <T, V> p); template <class T> void _print(vector <T> v); template <class T> void _print(set <T> v); template <class T, class V> void _print(map <T, V> v); template <class T> void _print(multiset <T> v); template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";} template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} void _print(pbds v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} //**************************// //************************************// ll expo(ll a,ll b,ll mod){ll ans=1;while(b>0){if(b&1){ans=(ans*a)%mod;}a=(a*a)%mod;b>>=1;}return ans;} ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);} ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N)) vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;} //************************************// ll rec(vvl &dp,vector<vector<char>>&g,int i, int j,int n){ if( i>n-1 || j>n-1) return 0; if(g[i][j]=='*') return 0; if(i==n-1 && j==n-1) return 1; if(dp[i][j]!=0) return dp[i][j]; ll cnt1=(rec(dp,g,i,j+1,n))%MOD;//right path ll cnt2=(rec(dp,g,i+1,j,n))%MOD;// down path dp[i][j]=(cnt1+cnt2)%MOD; return dp[i][j]; } void solve(){ // auto sgn = [&](int x) { // if (x > 0) return 1; // else return -1; // } int n; cin>>n; vector<vector<char>>g; for(int i=0;i<n;i++){ vector<char>g1; for(int j=0;j<n;j++){ char c; cin>>c; g1.pb(c); } g.pb(g1); } vvl dp(n,vector<ll>(n,0)); if(n==1) if(g[0][0]!='*') dp[0][0]=1; rec(dp,g,0,0,n); cout<<dp[0][0]<<endl; } int main(){ fastinout; #ifndef ONLINE_JUDGE freopen("Error.txt","w",stderr); #endif solve(); // vl x(n),y(n); // for(int i=0;i<n;i++){ // cin>>x[i]; // } // for(int i=0;i<n;i++){ // cin>>y[i]; // } //aise vector bnao and input lo fast tarika hai }