Untitled
unknown
plain_text
2 years ago
4.7 kB
7
Indexable
#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;
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
}Editor is loading...