fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pii pair<int, int>
  5. #define pii2 pair<pii, int>
  6. using namespace std;
  7.  
  8. const int N = 17;
  9. const int MASK = (1 << N);
  10. const int mod = 1e9 + 7;
  11. const int oo = 1e9;
  12.  
  13. int n, m, sx, sy, dp[N][MASK], c[N][N], ord = 0, ans = oo;
  14. char a[N][N];
  15. map <pii, int> s;
  16. int dx[5] = {0, 0, 0, -1, 1};
  17. int dy[5] = {0, 1, -1, 0, 0};
  18.  
  19. void bfs(int x, int y, int ord) {
  20.     vector <vector<bool>> vis(n + 1, vector<bool>(m + 1, 0));
  21.     vector <vector<int>> d(n + 1, vector<int>(m + 1, 0));
  22.     queue <pii> q;
  23.     q.push({x, y});
  24.     vis[x][y] = 1; d[x][y] = 0;
  25.     while(!q.empty()) {
  26.         pii t = q.front(); q.pop();
  27.         int x = t.fi;
  28.         int y = t.se;
  29.         for(int i = 1; i <= 4; i ++) {
  30.             int nx = x + dx[i];
  31.             int ny = y + dy[i];
  32.             if (!(0 <= nx && nx < n && 0 <= ny && ny < m)) continue;
  33.             if (a[nx][ny] == 'x') continue;
  34.             if (!vis[nx][ny]) {
  35.                 vis[nx][ny] = 1;
  36.                 d[nx][ny] = d[x][y] + 1;
  37.                 if (a[nx][ny] == '*' || a[nx][ny] == 'o') {
  38.                     int ord2 = s[{nx, ny}];
  39.                     c[ord][ord2] = d[nx][ny];
  40.                     c[ord2][ord] = d[nx][ny];
  41.                 }
  42.                 q.push({nx, ny});
  43.             }
  44.         }
  45.     }
  46. }
  47. void print(int mask) {
  48.     cout << bitset <5> (mask) << '\n' << '\n';
  49.     for(int mask = 0; mask < (1 << ord); mask ++) {
  50.         for(int i = 1; i <= ord; i ++) {
  51.             cout << dp[i][mask] << " ";
  52.         }
  53.         cout << '\n';
  54.     }
  55.     cout << '\n' << '\n';
  56. }
  57. void solve() {
  58.     while(cin >> m >> n) {
  59.         if (m == 0 && n == 0) return;
  60.         ans = oo;
  61.         ord = 0;
  62.         for(int i = 0; i < n; i ++)
  63.             for(int j = 0; j < m; j ++)
  64.                 cin >> a[i][j];
  65.  
  66.         for(int i = 0; i < n; i ++) {
  67.             for(int j = 0; j < m; j ++) {
  68.                 if (!(a[i][j] == '*' || a[i][j] == 'o')) continue;
  69.                 s[{i, j}] = ++ord;
  70.                 if (a[i][j] == 'o') {
  71.                     sx = i;
  72.                     sy = j;
  73.                 }
  74.             }
  75.         }
  76.         for(int i = 1; i <= ord; i ++) {
  77.             for(int j = 1; j <= ord; j ++) {
  78.                 c[i][j] = oo;
  79.             }
  80.         }
  81.         for(pii2 tt : s) {
  82.             pii t = tt.fi;
  83.             int t_ord = tt.se;
  84.             bfs(t.fi, t.se, t_ord);
  85.         }
  86.         for(int mask = 0; mask < (1 << ord); mask ++) {
  87.             for(int i = 1; i <= ord; i ++) {
  88.                 dp[i][mask] = oo;
  89.             }
  90.         }
  91.         int order = s[{sx, sy}];
  92.         dp[order][(1 << (order - 1))] = 0;
  93.         for(int mask = 0; mask < (1 << ord); mask ++) {
  94.             vector <int> pos;
  95.             for(int i = 0; i < ord; i ++) if ((mask >> i) & 1) pos.push_back(i);
  96.             for(int i : pos) for(int j : pos) {
  97.                 if (i == j) continue;
  98.                 dp[i + 1][mask] = min(dp[i + 1][mask], dp[j + 1][mask ^ (1 << i)] + c[i + 1][j + 1]);
  99.             }
  100.     //        print(mask);
  101.         }
  102.         for(int i = 1; i <= ord; i ++) {
  103.             ans = min(ans, dp[i][(1 << ord) - 1]);
  104.         }
  105.         cout << (ans == oo ? -1 : ans) << '\n';
  106.         s.clear();
  107.     }
  108. }
  109. signed main() {
  110.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  111.     solve();
  112. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fFklkc
language:
C++ (gcc 8.3)
created:
1 day 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!