Mission

input/code.cpp: In function 'int main()':
input/code.cpp:91:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < p.size(); ++i) {
                          ^

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> pp;

const int INF = 999999999;
int distAC[100];
int distBC[100];
int distCC[100][100];
int ay, ax;
int by, bx;
int w, h, k;
int cy[100], cx[100];
string m[110];
#define A first
#define B second
#define Y first
#define X second

int dist(int y1, int x1, int y2, int x2) {
  bool visited[101][101] = {0}; 
  priority_queue<pp, std::vector<pp>, std::greater<pp>> q;
  q.push(pp(0, ii(y1, x1)));
  visited[y1][x1] = true;
  while(!q.empty()) {
    pp t = q.top();
    ii p = t.B;
    q.pop();
    //if(visited[p.Y][p.X]) continue;
    for(int oy = -1; oy <= 1; ++oy) {
      for(int ox = -1; ox <= 1; ++ox) {
	if(abs(oy) + abs(ox) != 1) continue;
	int yy = p.Y + oy;
	int xx = p.X + ox;
	if(yy < 0 || yy >= h || xx < 0 || xx >= w) continue;
	if(yy == y2 && xx == x2) return t.A + 1;
	if(m[yy][xx] == '#' || m[yy][xx] == 'B') continue;
	if(visited[yy][xx]) continue;
	visited[yy][xx] = true;
	q.push(pp(t.A + 1, ii(yy, xx)));
      }
    }
  }
  throw;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> h >> w >> k;
  for(int y = 0; y < h; ++y) {
    cin >> m[y];
  }
  int idx = 0;
  for(int y = 0; y < h; ++y) {
    for(int x = 0; x < w; ++x) {
      if(m[y][x] == 'A') {
	ay = y;
	ax = x;
      }
      if(m[y][x] == 'B') {
	by = y;
	bx = x;
      }
      if(m[y][x] == '*') {
	cy[idx] = y;
	cx[idx] = x;
	++idx;
      }
    }
  }
  vector<int> p;
  for(int i = 0; i < k; ++i) {
    p.push_back(i);
    distAC[i] = dist(ay, ax, cy[i], cx[i]);
    distBC[i] = dist(by, bx, cy[i], cx[i]);
    for(int j = i + 1; j < k; ++j) {
      int d = dist(cy[i], cx[i], cy[j], cx[j]);
      distCC[i][j] = d;
      distCC[j][i] = d;
    }
  }
  if(p.empty()) {
    cout << dist(by, bx, ay, ax) << "\n";
    return 0;
  }
  int best = INF;
  do {
    int ans = distAC[p.front()] + distBC[p.back()];
    for(int i = 0; i + 1 < p.size(); ++i) {
      ans += distCC[p[i]][p[i + 1]];
    }
    best = min(best, ans);
  } while(next_permutation(p.begin(), p.end()));
  if(best == INF) throw;
  cout << best << "\n";
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED