fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> pii;
  5.  
  6. #define fi first
  7. #define sec second
  8.  
  9. const int MAX = 1005;
  10. const int mod = 1e9 + 7;
  11.  
  12. inline long long add(long long a, long long b) {
  13.   long long c = a + b;
  14.   return (c >= mod ? c - mod : c);
  15. }
  16.  
  17. inline long long sub(long long a, long long b) {
  18.   long long c = a - b;
  19.   return (c < 0 ? c + mod : c);
  20. }
  21.  
  22. inline long long mul(long long a, long long b) {
  23.   long long c = a * b;
  24.   return (c >= mod ? c % mod : c);
  25. }
  26.  
  27. int n;
  28. string s[3];
  29. int vis[3][MAX];
  30. long long dp[3][MAX][4][4];
  31. int pipe[4][4];
  32. pair<pii, pair<pii, pii>> trans[4][4];
  33.  
  34. void init() {
  35.   // index, entry
  36.   // entry, leave, go, candidate(pipe, entry)
  37.   for(int i = 0; i < 4; ++i) {
  38.     for(int j = 0; j < 4; ++j) {
  39.       pipe[i][j] = -1;
  40.       trans[i][j] = {{0, 0}, {{-1, -1}, {-1, -1}}};
  41.     }
  42.   }
  43.  
  44.   pipe[0][3] = 2;
  45.   pipe[0][2] = 3;
  46.  
  47.   pipe[1][1] = 2;
  48.   pipe[1][2] = 1;
  49.  
  50.   pipe[2][0] = 1;
  51.   pipe[2][1] = 0;
  52.  
  53.   pipe[3][3] = 0;
  54.   pipe[3][0] = 3;
  55.  
  56.   trans[0][1] = {{0, 1}, {{0, 3}, {3, 3}}};
  57.   trans[0][3] = {{0, -1}, {{1, 1}, {2, 1}}};
  58.  
  59.   trans[1][0] = {{-1, 0}, {{0, 2}, {1, 2}}};
  60.   trans[1][2] = {{1, 0}, {{2, 0}, {3, 0}}};
  61.  
  62.   trans[2][1] = {{0, 1}, {{0, 3}, {3, 3}}};
  63.   trans[2][3] = {{0, -1}, {{1, 1}, {2, 1}}};
  64.  
  65.   trans[3][0] = {{-1, 0}, {{0, 2}, {1, 2}}};
  66.   trans[3][2] = {{1, 0}, {{2, 0}, {3, 0}}};
  67. }
  68.  
  69. long long rec(int pos_x, int pos_y, int enter, int leave) {
  70.   // cout << pos_x << " " << pos_y << " " << enter << " " << leave << "\n";
  71.   if (pos_x < 0 || pos_x >= 3) {
  72.     // cout << "err 1\n";
  73.     return 0;
  74.   }
  75.   if (pos_y < 0 || pos_y >= n) {
  76.     // cout << "err 2\n";
  77.     return 0;
  78.   }
  79.   if (vis[pos_x][pos_y]) {
  80.     // cout << "err 3\n";
  81.     return 0;
  82.   }
  83.   if (s[pos_x][pos_y] == '#') {
  84.     // cout << "err 4\n";
  85.     return 0;
  86.   }
  87.   if (pos_x == 2 && pos_y == (n-1)) {
  88.     // cout << "Came " << leave << "\n";
  89.     if (leave == 1) {
  90.       return 1;
  91.     }
  92.     return 0;
  93.   }
  94.   long long &res = dp[pos_x][pos_y][enter][leave];
  95.   if (res != -1) {
  96.     return res;
  97.   }
  98.   res = 0;
  99.   auto get = trans[enter][leave];
  100.   pii go = get.fi;
  101.   auto can = get.sec;
  102.  
  103.   vis[pos_x][pos_y] = 1;
  104.   res = add(res, rec(pos_x + go.fi, pos_y + go.sec,
  105.                      can.fi.sec, pipe[can.fi.fi][can.fi.sec]));
  106.   vis[pos_x][pos_y] = 0;
  107.  
  108.   vis[pos_x][pos_y] = 1;
  109.   res = add(res, rec(pos_x + go.fi, pos_y + go.sec,
  110.                      can.sec.sec, pipe[can.sec.fi][can.sec.sec]));
  111.   vis[pos_x][pos_y] = 0;
  112.  
  113.   return res;
  114. }
  115.  
  116.  
  117. int main() {
  118.   ios_base::sync_with_stdio(false);
  119.   init();
  120.   int T;
  121.   cin >> T;
  122.   for(int t = 1; t <= T; ++t) {
  123.     cin >> n;
  124.     cin >> s[0] >> s[1] >> s[2];
  125.     for(int i = 0; i < 3; ++i) {
  126.       for(int j = 0; j < n; ++j) {
  127.         vis[i][j] = 0;
  128.         for(int k = 0; k < 4; ++k) {
  129.           for(int l = 0; l < 4; ++l) {
  130.             dp[i][j][k][l] = -1;
  131.           }
  132.         }
  133.       }
  134.     }
  135.     long long ans = rec(0, 0, 1, 2);
  136.     cout << "Case #" << t << ": " << ans << "\n";
  137.   }
  138.   return 0;
  139. }
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
7
2
..
..
..
2
#.
..
.#
4
...#
....
.#..
4
..##
....
.#..
5
.#...
.....
.....
8
....#...
........
#.......
70
......................................................................
......................................................................
......................................................................
stdout
copy 
Case #1: 1
Case #2: 0
Case #3: 1
Case #4: 0
Case #5: 0
Case #6: 4
Case #7: 179869065
https://ideone.com/weEJ8T
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!