fork download
  1. #include <bits/stdc++.h>
  2. #include <chrono>
  3. using namespace std;
  4. using namespace chrono;
  5. // "AJEET JAIN"----"JAI JINENDRA"
  6. /* "णमो अरिहंताणं",
  7.   "णमो सिद्धाणं",
  8.   "णमो आयरियाणं",
  9.   "णमो उवज्झायाणं",
  10.   "णमो लोए सव्वसाहूणं",
  11.   "",
  12.   "एसो पंच नमोक्कारो, सव्व पावप्पणासणो",
  13.   "मंगलाणं च सव्वेसिं, पडमं हवै मंगलं", */
  14.  
  15.  
  16. // Aliases to op
  17. using ll = long long;
  18. using ull = unsigned long long;
  19. using ld = double;
  20. using vll = vector<ll>;
  21.  
  22.  
  23. // Constants
  24. constexpr ll INF = 4e18;
  25. constexpr ld EPS = 1e-9;
  26. constexpr ll MOD = 1e9 + 7;
  27.  
  28.  
  29.  
  30. // Macros
  31. #define F first
  32. #define S second
  33. #define all(x) begin(x), end(x)
  34. #define allr(x) rbegin(x), rend(x)
  35. #define py cout<<"YES\n";
  36. #define pn cout<<"NO\n";
  37. #define forn(i,n) for(int i=0;i<n;i++)
  38. #define for1(i,n) for(int i=1;i<=n;i++)
  39.  
  40. // #define insert push_back
  41. #define pb push_back
  42. #define MP make_pair
  43. #define endl '\n'
  44.  
  45. /*
  46.   ROUGH --
  47.  
  48.   */
  49.  
  50. void AJNJ(){
  51. ll n;
  52. cin >> n;
  53. vector<vector<char>>v(n+1 , vector<char>(n+1 , 0));
  54. ll dp[n+1][n+1];
  55. for1(i , n){
  56. for1(j , n){
  57. cin >> v[i][j];
  58. }
  59. }
  60.  
  61. for(int i = n ; i >= 0 ; i--){
  62. for1(j , n){
  63. if(i == n){
  64. if(v[i][j] == '.'){
  65. dp[i][j] = 1;
  66. }
  67. else{
  68. dp[i][j] = 0;
  69. }
  70. }
  71. else{
  72. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1];
  73. }
  74. }
  75. }
  76. ll ans = 0;
  77. for1(j , n){
  78. ans = (ans%MOD + dp[1][j]%MOD)%MOD;
  79. }
  80.  
  81. cout << ans << endl;
  82.  
  83.  
  84. }
  85.  
  86.  
  87. int main(){
  88. ios::sync_with_stdio(0);
  89. cin.tie(0);
  90. cout.tie(0);
  91. int T = 1;
  92. cin>>T;
  93. auto start1 = high_resolution_clock::now();
  94. while(T--){
  95. AJNJ();
  96. }
  97. auto stop1 = high_resolution_clock::now();
  98. auto duration = duration_cast<microseconds>(stop1 - start1);
  99. cerr << "Time: " << duration . count() / 1000 << " ms" << endl;
  100.  
  101. return 0;
  102. }
Success #stdin #stdout #stderr 0.01s 5320KB
stdin
Standard input is empty
stdout
0
stderr
Time: 0 ms