Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define print_var(x) cerr << #x << " = " << x << endl
- #define print_array(arr, len) {cerr << #arr << " = "; for (int i = 0; i < len; i++) cerr << arr[i] << " "; cerr << endl;}
- #define print_iterable(it) {cerr << #it << " = "; for (const auto &e : it) cerr << e << " "; cerr << endl;}
- #else
- #define eprintf(...) (void)0
- #define print_var(x) (void)0
- #define print_array(arr, len) (void)0
- #define print_iterable(it) (void)0
- #endif
- typedef long long ll;
- const int DX[] = {1, 0, -1, 0};
- const int DY[] = {0, 1, 0, -1};
- const int INF = (int)1e8;
- const int K = 7;
- const int N = 110;
- char table[N][N];
- int n, m;
- int k;
- pair<int, int> points[K];
- int dist[K][N][N];
- bool read()
- {
- scanf("%d%d", &n, &m);
- if (n + m == 0)
- return false;
- for (int i = 0; i < n; i++)
- scanf(" %s", table[i]);
- scanf("%d", &k);
- for (int i = 0; i < k; i++)
- {
- scanf("%d%d", &points[i].first, &points[i].second);
- points[i].first--;
- points[i].second--;
- }
- return true;
- }
- void put_start()
- {
- for (int i = 0; i < n; i++)
- {
- for (int s = 0; s < m; s++)
- {
- if (table[i][s] == '@')
- points[k] = make_pair(i, s);
- }
- }
- }
- pair<int, int> q[N * N];
- bool valid_cell(int x, int y)
- {
- if (x < 0 || y < 0 || x >= n || y >= m)
- return false;
- return table[x][y] != '@';
- }
- void calc_dist(pair<int, int> start, int cur_dist[N][N])
- {
- for (int i = 0; i < n; i++)
- for (int s = 0; s < m; s++)
- cur_dist[i][s] = INF;
- cur_dist[start.first][start.second] = 0;
- int r = 0;
- q[r++] = start;
- for (int i = 0; i < r; i++)
- {
- auto v = q[i];
- for (int d = 0; d < 4; d++)
- {
- int nx = v.first + DX[d];
- int ny = v.second + DY[d];
- if (valid_cell(nx, ny) && cur_dist[nx][ny] > cur_dist[v.first][v.second] + 1)
- {
- q[r++] = make_pair(nx, ny);
- cur_dist[v.first][v.second] = cur_dist[nx][ny] + 1;
- }
- }
- }
- }
- void solve()
- {
- put_start();
- vector <int> perm = {};
- for (int i = 0; i <= k; i++)
- {
- calc_dist(points[i], dist[i]);
- perm.push_back(i);
- }
- swap(perm[k], perm[0]);
- int ans = INF;
- do
- {
- int loc_ans = 0;
- for (int i = 0; i < k; i++)
- {
- auto next_pos = points[perm[i + 1]];
- loc_ans += dist[perm[i]][next_pos.first][next_pos.second];
- }
- ans = min(ans, loc_ans);
- } while (next_permutation(perm.begin() + 1, perm.end()));
- if (ans == INF)
- puts("-1");
- else
- printf("%d\n", ans);
- }
- int main()
- {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- while (read())
- solve();
- eprintf("\n\ntime = %.3lf\n", (double)clock() / CLOCKS_PER_SEC);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement