Advertisement
Guest User

Untitled

a guest
Dec 14th, 2018
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 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> dp[24][24];
  26. const int allon = (1 << 21) - 1;
  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. int dfs(int r, int c, int m) {
  35.   if (m == allon) {
  36.     return 1;
  37.   } else if (dp[r][c].count(m) != 0) {
  38.     return dp[r][c][m];
  39.   } else {
  40.     int res = 0;
  41.     for (int d = 0; d < 4; ++d) {
  42.       int r1 = r + dr[d], c1 = c + dc[d];
  43.       if (in(r1, c1)) {
  44.         int b = grid[r1][c1];
  45.         if (b != -1 && (m & (1 << b)) == 0) {
  46.           res += dfs(r1, c1, m | (1 << b));
  47.         }
  48.       }
  49.     }
  50.     return dp[r][c][m] = res;
  51.   }
  52. }
  53.  
  54. void _SOLVE_() {
  55.   cin >> R >> C;
  56.   memset(grid, -1, sizeof(grid));
  57.   for (int r = 1; r <= R; ++r) {
  58.     for (int c = 1; c <= C; ++c) {
  59.       string s;
  60.       cin >> s;
  61.       if (s[0] != '_') {
  62.         grid[r][c] = 10*(s[1] - '0') + (s[2] - '0') - 1;
  63.       }
  64.     }
  65.   }
  66.   int ans = 0;
  67.   for (int r = 1; r <= R; ++r) {
  68.     for (int c = 1; c <= C; ++c) {
  69.       if (grid[r][c] != -1) {
  70.         ans += dfs(r, c, 1 << grid[r][c]);
  71.       }
  72.     }
  73.   }
  74.   cout << ans << endl;
  75. }
  76.  
  77.  
  78. int main() {
  79.   ios::sync_with_stdio(false);
  80.   cin.tie(nullptr);
  81.   #ifdef _DEBUG
  82.   freopen("in.txt", "r", stdin);
  83.   freopen("out.txt", "w", stdout);
  84.   #endif
  85.   _SOLVE_();
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement