Advertisement
Guest User

Untitled

a guest
Dec 14th, 2018
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.51 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef pair<int, int> pi;
  9. typedef pair<ll, ll> pl;
  10. typedef pair<ld, ld> pd;
  11. typedef vector<int> vi;
  12. typedef vector<ll> vl;
  13. typedef vector<ld> vd;
  14. typedef vector<pi> vpi;
  15. typedef vector<pl> vpl;
  16. template <class Key, class Compare = less<Key>> // find_by_order, order_of_key (for multiset: pair(val, time of insertion))
  17. using Tree = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
  18.  
  19.  
  20.  
  21.  
  22.  
  23. int R, C;
  24. int grid[24][24];
  25. map<int, int> cnt[24][24];
  26. int ans;
  27.  
  28. int dr[4] = {-1, 0, 1, 0};
  29. int dc[4] = {0, 1, 0, -1};
  30. inline bool in(int r, int c) {
  31.   return r >= 1 && r <= R && c >= 1 && c <= C;
  32. }
  33.  
  34. void dfs1(int m, int len, int r, int c) {
  35.   if (len == 10) {
  36.     ++cnt[r][c][m];
  37.   } else {
  38.     for (int d = 0; d < 4; ++d) {
  39.       int r1 = r + dr[d], c1 = c + dc[d];
  40.       int b = grid[r1][c1];
  41.       if (b != -1 && (m & (1 << b)) == 0) {
  42.         dfs1(m | (1 << b), len + 1, r1, c1);
  43.       }
  44.     }
  45.   }
  46. }
  47.  
  48. void dfs2(int m, int len, int r, int c) {
  49.   if (len == 11) {
  50.     int inverse = ((1 << 21) - 1) & ~m;
  51.     for (int d = 0; d < 4; ++d) {
  52.       int r1 = r + dr[d], c1 = c + dc[d];
  53.       if (in(r1, c1)) {
  54.         ans += cnt[r1][c1][inverse];
  55.       }
  56.     }
  57.   } else {
  58.     for (int d = 0; d < 4; ++d) {
  59.       int r1 = r + dr[d], c1 = c + dc[d];
  60.       int b = grid[r1][c1]; //weird order but whatever (should check if in(r1,c1) first)
  61.       if (in(r1, c1) && b != -1 && (m & (1 << b)) == 0) {
  62.         dfs2(m | (1 << b), len + 1, r1, c1);
  63.       }
  64.     }
  65.   }
  66. }
  67.  
  68. void _SOLVE_() {
  69.   cin >> R >> C;
  70.   memset(grid, -1, sizeof(grid));
  71.   for (int r = 1; r <= R; ++r) {
  72.     for (int c = 1; c <= C; ++c) {
  73.       string s;
  74.       cin >> s;
  75.       if (s[0] != '_') {
  76.         grid[r][c] = 10*(s[1] - '0') + (s[2] - '0') - 1;
  77.       }
  78.     }
  79.   }
  80.   ans = 0;
  81.   for (int r = 1; r <= R; ++r) {
  82.     for (int c = 1; c <= C; ++c) {
  83.       if (grid[r][c] != -1) {
  84.         dfs1(1 << grid[r][c], 1, r, c);
  85.       }
  86.     }
  87.   }
  88.   for (int r = 1; r <= R; ++r) {
  89.     for (int c = 1; c <= C; ++c) {
  90.       if (grid[r][c] != -1) {
  91.         dfs2(1 << grid[r][c], 1, r, c);
  92.       }
  93.     }
  94.   }
  95.   cout << ans << endl;
  96. }
  97.  
  98.  
  99. int main() {
  100.   ios::sync_with_stdio(false);
  101.   cin.tie(nullptr);
  102.   #ifdef _DEBUG
  103.   freopen("in.txt", "r", stdin);
  104.   freopen("out.txt", "w", stdout);
  105.   #endif
  106.   _SOLVE_();
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement