SHARE
TWEET

Untitled

a guest Apr 21st, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int n, m, dp[(1 << 17)], dist[25][25];
  6. int f[55][55], cc;
  7. char a[55][55];
  8. bool is[55][55];
  9. bool was[55];
  10.  
  11. void dfs(int x, int y) {
  12.         is[x][y] = 1;
  13.         f[x][y] = cc;
  14.         if (a[x - 1][y] == 'X' && !is[x - 1][y]) dfs(x - 1, y);
  15.         if (a[x + 1][y] == 'X' && !is[x + 1][y]) dfs(x + 1, y);
  16.         if (a[x][y - 1] == 'X' && !is[x][y - 1]) dfs(x, y - 1);
  17.         if (a[x][y + 1] == 'X' && !is[x][y + 1]) dfs(x, y + 1);
  18. }
  19.  
  20. struct per{
  21.     int x, y, dist;
  22.     per(int x = 0, int y = 0, int dist = 0) : x(x), y(y), dist(dist) {}
  23. };
  24.  
  25. main() {
  26. #ifdef ONPC
  27.     freopen("a.in", "r", stdin);
  28. #endif
  29.     ios_base::sync_with_stdio(0), cin.tie(0);
  30.     cin >> n >> m;
  31.     for (int i = 0; i < 25; ++i)
  32.         for (int j = 0; j < 25; ++j)
  33.             dist[i][j] = 1e9 + 7;
  34.     for (int i = 1; i <= n; ++i) {
  35.         for (int j = 1; j <= m; ++j) {
  36.             cin >> a[i][j];
  37.         }
  38.     }
  39.     for (int i = 1; i <= n; ++i) {
  40.         for (int j = 1; j <= m; ++j) {
  41.             if (a[i][j] == 'X' && !is[i][j]) {
  42.                 ++cc;
  43.                 dfs(i, j);
  44.             }
  45.         }
  46.     }
  47.     for (int i = 1; i <= n; ++i) {
  48.         for (int j = 1; j <= m; ++j) {
  49.             if (a[i][j] != 'X') continue;
  50.             if (was[f[i][j]]) continue;
  51.             was[f[i][j]] = 1;
  52.             deque<per> Q;
  53.             Q.push_back(per(i, j, 0));
  54.             for (int x = 0; x < 55; ++x)
  55.                 for (int y = 0; y < 55; ++y)
  56.                     is[x][y] = 0;
  57.             is[i][j] = 1;
  58.             while(!Q.empty()) {
  59.                 auto t = Q.front();
  60.                 int x = t.x, y = t.y;
  61.                 Q.pop_front();
  62.                 if (a[x - 1][y] == 'X' && !is[x - 1][y]) Q.push_front(per(x - 1, y, t.dist)), is[x - 1][y] = 1;
  63.                 if (a[x - 1][y] == 'S' && !is[x - 1][y]) Q.push_back(per(x - 1, y, t.dist + 1)), is[x - 1][y] = 1;
  64.                 if (a[x + 1][y] == 'X' && !is[x + 1][y]) Q.push_front(per(x + 1, y, t.dist)), is[x + 1][y] = 1;
  65.                 if (a[x + 1][y] == 'S' && !is[x + 1][y]) Q.push_back(per(x + 1, y, t.dist + 1)), is[x + 1][y] = 1;
  66.                 if (a[x][y - 1] == 'X' && !is[x][y - 1]) Q.push_front(per(x, y - 1, t.dist)), is[x][y - 1] = 1;
  67.                 if (a[x][y - 1] == 'S' && !is[x][y - 1]) Q.push_back(per(x, y - 1, t.dist + 1)), is[x][y - 1] = 1;
  68.                 if (a[x][y + 1] == 'X' && !is[x][y + 1]) Q.push_front(per(x, y + 1, t.dist)), is[x][y + 1] = 1;
  69.                 if (a[x][y + 1] == 'S' && !is[x][y + 1]) Q.push_back(per(x, y + 1, t.dist + 1)), is[x][y + 1] = 1;
  70.                 if (a[x][y] == 'X')
  71.                     dist[f[i][j]][f[x][y]] = min(dist[f[i][j]][f[x][y]], t.dist);
  72.             }
  73.         }
  74.     }
  75.     for (int i = 0; i < (1 << 17); ++i) dp[i] = 1e9 + 7;
  76.     for (int i = 1; i <= cc; ++i) dp[(1 << (cc - 1))] = 0;
  77.     dp[0] = 0;
  78.     for (int mask = 0; mask < (1 << cc) - 1; ++mask) {
  79.         for (int j = 1; j <= cc; ++j) {
  80.             if ((mask & (1 << (j - 1))) == 0) continue;
  81.             for (int i = 1; i <= cc; ++i) {
  82.                 if ((mask & (1 << (i - 1))) != 0) continue;
  83.                 dp[mask | (1 << (i - 1))] = min(dp[mask | (1 << (i - 1))], dp[mask] + dist[i][j]);
  84.             }
  85.         }
  86.     }
  87.     cout << dp[(1 << cc) - 1] << '\n';
  88.     return 0;
  89. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top