fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MOD 1000000007
  5. #define PI 3.1415926535897932384
  6. #define fastio std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  7. #define int long long
  8.  
  9. int dp[1005][3][2];
  10.  
  11. int findans(int i, int j, int state, vector <string> vv, int n){
  12.  
  13.  
  14.     if(i >= n || i < 0 || j < 0 || j >= 3) return 0;
  15.     if(i == n-1 && j == 2 && state == 1)   return 1;
  16.     int ans = 0;
  17.     if(state){
  18.         if(i+1 < n && vv[j][i+1] != '#'){
  19.             if(dp[i+1][j][1-state] != -1)
  20.                 ans = (ans + dp[i+1][j][1-state])%MOD;
  21.             else
  22.                 ans = (ans + findans(i+1, j, 1-state, vv, n))%MOD;
  23.         }
  24.         return dp[i][j][state] = ans;
  25.     }
  26.     else{
  27.         if(j+1 < 3 && vv[j+1][i] != '#'){
  28.             if(dp[i][j+1][1-state] != -1)
  29.                 ans = (ans + dp[i][j+1][1-state])%MOD;
  30.             else
  31.                 ans = (ans + findans(i, j+1, 1-state, vv, n))%MOD;
  32.         }
  33.         if(j-1 >= 0 && vv[j-1][i] != '#'){
  34.             if(dp[i][j-1][1-state] != -1)
  35.                 ans = (ans + dp[i][j-1][1-state]);
  36.             else
  37.                 ans = (ans + findans(i, j-1, 1-state, vv, n))%MOD;
  38.         }
  39.         return dp[i][j][state] = ans;
  40.     }
  41.     return 0;
  42. }
  43.  
  44. void solve(int t){
  45.     int n;
  46.     cin >> n;
  47.     vector <string> vv;
  48.     string s;
  49.     cin >> s; vv.push_back(s);
  50.     cin >> s; vv.push_back(s);
  51.     cin >> s; vv.push_back(s);
  52.  
  53.     cout << "Case #" << t << ": ";
  54.     //bool visited;
  55.     for(int i = 0; i < n; i++){
  56.         for(int j = 0; j < 3; j++){
  57.             for(int k = 0; k < 2; k++){
  58.                 dp[i][j][k] = -1;
  59.             }
  60.         }
  61.     }
  62.  
  63.     cout << findans(0, 0, 0, vv, n) << "\n";
  64.  
  65. }
  66.  
  67. signed main(){
  68.  
  69.     fastio;
  70.  
  71.     int t;
  72.     cin >> t;
  73.     for(int i = 1; i <= t; i++){
  74.         solve(i);
  75.     }
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mADXsz
language:
C++14 (gcc 8.3)
created:
5 years 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!