Mission

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <stack>

using namespace std;

#define all(x) (x).begin(),x.end()
#define ii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long

#define MAXN 101
#define INF 1000000007

int nR, nC, nCoin;
int a[MAXN][MAXN];
vector<int> eList[20], cList[20];
int d[MAXN][MAXN];

bool mark[20];
int res, cur, exitNode;

int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

void bfs(int si, int sj) {
	queue<ii> q;
	int i = a[si][sj];
	q.push(ii(si, sj));

	memset(d, -1, sizeof(d));
	d[si][sj] = 0;

	while (!q.empty()) {
		ii top = q.front();
		q.pop();

		if (a[top.fi][top.se] > 0) {
			int j = a[top.fi][top.se];
			eList[i].pb(j);
			cList[i].pb(d[top.fi][top.se]);
		}

		for (int k = 0; k < 4; k++) {
			int r = top.fi + dx[k];
			int c = top.se + dy[k];
			if (r < 0 || r >= nR || c < 0 || c >= nC || a[r][c] == -1) {
				continue;
			}

			if (d[r][c] == -1) {
				d[r][c] = d[top.fi][top.se] + 1;
				q.push(ii(r, c));

			}
		}
	}
} 

void dfs(int i) {
	if (i == exitNode) {
		bool found = false;
		for (int k = 2; k < exitNode; k++) {
			if (mark[k] == false) {
				found = true;
				break;
			}
		}
		if (!found && cur < res) {
			res = cur;
		}

		return;
	}

	for (int k = 0; k < (int)eList[i].size(); k++) {
		int j = eList[i][k];
		if (mark[j]) {
			continue;
		}

		mark[j] = true;
		cur += cList[i][k];
		dfs(j);

		mark[j] = false;
		cur -= cList[i][k];
	}
}

int main() {
	memset(a, 0, sizeof(a));

	cin >> nR >> nC >> nCoin;
	char tmp;
	int count = 2;
	exitNode = nCoin + 2;
	for (int i = 0; i < nR; i++) {
		for (int j = 0; j < nC; j++) {
			cin >> tmp;
			if (tmp == '#') {
				a[i][j] = -1;
			} else if (tmp == 'A') {
				a[i][j] = 1;
			} else if (tmp == '*') {
				a[i][j] = count;
				count++;
			} else if (tmp == 'B') {
				a[i][j] = exitNode;
			}
		}
	}

	for (int i = 0; i < nR; i++) {
		for (int j = 0; j < nC; j++) {
			if (a[i][j] > 0) {
				bfs(i, j);
			}
		}
	}

	res = INF;
	cur = 0;
	memset(mark, 0, sizeof(mark));
	mark[1] = true;
	dfs(1);

	cout << res;
	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