Advertisement
Guest User

Untitled

a guest
Mar 26th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  6. #define print_var(x) cerr << #x << " = " << x << endl
  7. #define print_array(arr, len) {cerr << #arr << " = "; for (int i = 0; i < len; i++) cerr << arr[i] << " "; cerr << endl;}
  8. #define print_iterable(it) {cerr << #it << " = "; for (const auto &e : it) cerr << e << " "; cerr << endl;}
  9. #else
  10. #define eprintf(...) (void)0
  11. #define print_var(x) (void)0
  12. #define print_array(arr, len) (void)0
  13. #define print_iterable(it) (void)0
  14. #endif
  15.  
  16. typedef long long ll;
  17.  
  18. const int DX[] = {1, 0, -1, 0};
  19. const int DY[] = {0, 1, 0, -1};
  20. const int INF = (int)1e8;
  21. const int K = 7;
  22. const int N = 110;
  23. char table[N][N];
  24. int n, m;
  25. int k;
  26. pair<int, int> points[K];
  27. int dist[K][N][N];
  28.  
  29. bool read()
  30. {
  31.     scanf("%d%d", &n, &m);
  32.     if (n + m == 0)
  33.         return false;
  34.     for (int i = 0; i < n; i++)
  35.         scanf(" %s", table[i]);
  36.     scanf("%d", &k);
  37.     for (int i = 0; i < k; i++)
  38.     {
  39.         scanf("%d%d", &points[i].first, &points[i].second);
  40.         points[i].first--;
  41.         points[i].second--;
  42.     }
  43.     return true;
  44. }
  45.  
  46. void put_start()
  47. {
  48.     for (int i = 0; i < n; i++)
  49.     {
  50.         for (int s = 0; s < m; s++)
  51.         {
  52.             if (table[i][s] == '@')
  53.                 points[k] = make_pair(i, s);
  54.         }
  55.     }
  56. }
  57.  
  58. pair<int, int> q[N * N];
  59.  
  60. bool valid_cell(int x, int y)
  61. {
  62.     if (x < 0 || y < 0 || x >= n || y >= m)
  63.         return false;
  64.     return table[x][y] != '@';
  65. }
  66.  
  67. void calc_dist(pair<int, int> start, int cur_dist[N][N])
  68. {
  69.     for (int i = 0; i < n; i++)
  70.         for (int s = 0; s < m; s++)
  71.             cur_dist[i][s] = INF;
  72.     cur_dist[start.first][start.second] = 0;
  73.     int r = 0;
  74.     q[r++] = start;
  75.     for (int i = 0; i < r; i++)
  76.     {
  77.         auto v = q[i];
  78.         for (int d = 0; d < 4; d++)
  79.         {
  80.             int nx = v.first + DX[d];
  81.             int ny = v.second + DY[d];
  82.             if (valid_cell(nx, ny) && cur_dist[nx][ny] > cur_dist[v.first][v.second] + 1)
  83.             {
  84.                 q[r++] = make_pair(nx, ny);
  85.                 cur_dist[v.first][v.second] = cur_dist[nx][ny] + 1;
  86.             }
  87.         }
  88.     }
  89. }
  90.  
  91. void solve()
  92. {
  93.     put_start();
  94.     vector <int> perm = {};
  95.     for (int i = 0; i <= k; i++)
  96.     {
  97.         calc_dist(points[i], dist[i]);
  98.         perm.push_back(i);
  99.     }
  100.     swap(perm[k], perm[0]);
  101.     int ans = INF;
  102.     do
  103.     {
  104.         int loc_ans = 0;
  105.         for (int i = 0; i < k; i++)
  106.         {
  107.             auto next_pos = points[perm[i + 1]];
  108.             loc_ans += dist[perm[i]][next_pos.first][next_pos.second];
  109.         }
  110.         ans = min(ans, loc_ans);
  111.     } while (next_permutation(perm.begin() + 1, perm.end()));
  112.     if (ans == INF)
  113.         puts("-1");
  114.     else
  115.         printf("%d\n", ans);
  116. }
  117.  
  118. int main()
  119. {
  120. #ifdef LOCAL
  121.     freopen("input.txt", "r", stdin);
  122. #endif
  123.  
  124.     while (read())
  125.         solve();
  126.  
  127.     eprintf("\n\ntime = %.3lf\n", (double)clock() / CLOCKS_PER_SEC);
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement