Mission

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <set>
#include <deque>

typedef long long LL;

using namespace std;
LL n,m,k;

class Node{
  
public:
    int r,c,dist;
    Node(int r, int c, int dist){
        this->r = r;
        this->c = c;
        this->dist = dist;
    }
};

bool free(int r, int c, vector<vector<char> >& grid){
    return grid[r][c] != '#';
}

void bfs(int r, int c, int start, vector<vector<char> >& grid, vector<vector<int> >& D){
    
    deque<Node> Q;
    vector<vector<char> > visited(n, vector<char>(m));
    Q.push_back(Node(r,c,0));
    while(!Q.empty()){
        auto v = Q.front(); Q.pop_front();
        r = v.r; 
        c = v.c;
        if(visited[r][c]) continue;
        visited.at(r).at(c) = 1;
        
        char symbol = grid[r][c];
        if(symbol >= '0' && symbol <= '9'){
            D[start][symbol-'0'] = v.dist;
            D[symbol-'0'][start] = v.dist;
        }
        
        if(r > 0 && free(r-1, c, grid)){
            Node u(r-1,c,v.dist+1);
            Q.push_back(u);
        }
        if(r < n-1 && free(r+1, c, grid)) {
            Node u(r+1,c,v.dist+1);
            Q.push_back(u);
        }
        if(c > 0 && free(r, c-1, grid)){
            Node u(r,c-1,v.dist+1);
            Q.push_back(u);
        }
        if(c < m-1 && free(r, c+1, grid)){
            Node u(r,c+1,v.dist+1);
            Q.push_back(u);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    
    vector<vector<char> > grid(n, vector<char>(m));
    map<int,pair<int,int> > special;
    int coin_counter = 1;
    for(int i = 0; i < n; i++){
        string line; cin >> line;
        for(int j = 0; j < line.size(); j++){
            grid[i][j] = line[j]; 
            if(line[j] == '*'){
                grid[i][j] = '0' + coin_counter;
                special[coin_counter] = {i,j};
                coin_counter++;
            }
            else if(line[j] == 'A'){
                special[0] = {i,j};
                grid[i][j] = '0';
            }
            else if(line[j] == 'B'){
                special[k+1] = {i,j};
                grid[i][j] = '0' + k + 1;
            }
        }
        //for(auto c : grid[i]) cout << c; cout << endl;
    }
    
    vector<vector<int> > D(k+2, vector<int>(k+2));
    
    for(auto keyvalue : special){
        int id = keyvalue.first;
        int r = keyvalue.second.first;
        int c = keyvalue.second.second;
        bfs(r, c, id, grid, D);
    }
    
    if(k == 0){
        cout << D[0][k+1] <<  endl;
        return 0;
    }
    
    /*
    for(int i = 0; i < k+2; i++){
        for(int j = 0; j < k+2; j++){
            cout << D[i][j] << " ";
        }
        cout << endl;
    } */
    
    vector<int> permutation;
    for(int i = 1; i <= k; i++){
        permutation.push_back(i);
    }

    LL ans = 1e9;
    do {
        LL score = 0;
        for(int i = 0; i < k-1; i++){
            score += D[permutation[i]][permutation[i+1]];
        }
        score += D[0][permutation[0]];
        score += D[permutation.back()][k+1];
        ans = min(ans,score);
    } while (next_permutation(permutation.begin(), permutation.end()) );
    
    cout << ans << endl;
    
}

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