fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5.  
  6. int t, h, w;
  7. vector<string> grid;
  8. vector<pair<int,int>> boxPos, targetPos;
  9. int distBFS[50][50];
  10.  
  11. int dh[4] = {1, -1, 0, 0};
  12. int dw[4] = {0, 0, 1, -1};
  13.  
  14.  
  15. int main() {
  16.     cin >> t;
  17.     while (t--) {
  18.         cin >> h >> w;
  19.         grid.resize(h);
  20.         for (int i = 0; i < h; i++) cin >> grid[i];
  21.  
  22.         boxPos.clear();
  23.         targetPos.clear();
  24.  
  25.         for (int i = 0; i < h; i++) {
  26.             for (int j = 0; j < w; j++) {
  27.                 if (grid[i][j] == 'B') boxPos.push_back({i,j});
  28.                 if (grid[i][j] == 'X') targetPos.push_back({i,j});
  29.             }
  30.         }
  31.  
  32.         int n = boxPos.size();
  33.         int m = targetPos.size();
  34.  
  35.         vector<vector<int>> A(n+1, vector<int>(m+1, INF));
  36.  
  37.         for (int b = 0; b < n; b++) {
  38.             for (int i = 0; i < h; i++)
  39.                 for (int j = 0; j < w; j++)
  40.                     distBFS[i][j] = INF;
  41.  
  42.             queue<pair<int,int>> q;
  43.             auto [sx, sy] = boxPos[b];
  44.             distBFS[sx][sy] = 0;
  45.             q.push({sx, sy});
  46.  
  47.             while (!q.empty()) {
  48.                 auto [x, y] = q.front(); q.pop();
  49.                 for (int k = 0; k < 4; k++) {
  50.                     int nx = x + dh[k], ny = y + dw[k];
  51.                     if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
  52.                     if (grid[nx][ny] == '#') continue;
  53.                     if (distBFS[nx][ny] > distBFS[x][y] + 1) {
  54.                         distBFS[nx][ny] = distBFS[x][y] + 1;
  55.                         q.push({nx, ny});
  56.                     }
  57.                 }
  58.             }
  59.  
  60.             for (int t = 0; t < m; t++) {
  61.                 auto [tx, ty] = targetPos[t];
  62.                 A[b+1][t+1] = distBFS[tx][ty];
  63.             }
  64.         }
  65.  
  66.         vector<int> u(n+1), v(m+1), p(m+1), way(m+1);
  67.  
  68.         for (int i = 1; i <= n; ++i) {
  69.             p[0] = i;
  70.             int j0 = 0;
  71.             vector<int> minv(m+1, INF);
  72.             vector<bool> used(m+1, false);
  73.             do {
  74.                 used[j0] = true;
  75.                 int i0 = p[j0], delta = INF, j1 = 0;
  76.                 for (int j = 1; j <= m; ++j)
  77.                     if (!used[j]) {
  78.                         int cur = A[i0][j] - u[i0] - v[j];
  79.                         if (cur < minv[j])
  80.                             minv[j] = cur, way[j] = j0;
  81.                         if (minv[j] < delta)
  82.                             delta = minv[j], j1 = j;
  83.                     }
  84.                 for (int j = 0; j <= m; ++j)
  85.                     if (used[j])
  86.                         u[p[j]] += delta, v[j] -= delta;
  87.                     else
  88.                         minv[j] -= delta;
  89.                 j0 = j1;
  90.             } while (p[j0] != 0);
  91.  
  92.             do {
  93.                 int j1 = way[j0];
  94.                 p[j0] = p[j1];
  95.                 j0 = j1;
  96.             } while (j0);
  97.         }
  98.  
  99.         int answer = -v[0];
  100.         cout << answer << endl;
  101.     }
  102.  
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/q6Pwg9
language:
C++14 (clang 8.0)
created:
4 days 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!