UVA 10888

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;

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

int h,w;
char grid[40][40];
int dist[15][15];
int x_sz = 0;

bool valid(int r, int c) {
    return (r >= 0 && r < h && c >= 0 && c < w && grid[r][c] != '#');
}

int mem[15][32799];
int solve(int idx, int msk) {
    if(idx == x_sz) {
        return 0;
    }
    if(mem[idx][msk] != -1) {
        return mem[idx][msk];
    }
    int &ret = mem[idx][msk];
    ret = 1e9;
    for(int i = 0; i < x_sz; i++) {
        int cm = (1 << i);
        //cout << "dist[" << idx << "][" << i << "] = " << dist[idx][i] << "\n";
        if(!(msk&cm) && dist[idx][i] != 1e9) {
            int new_msk = msk | cm;
            ret = min(ret,dist[idx][i]+solve(idx+1,new_msk));
        }
    }
    //cout << "at idx = " << idx << " msk = " << msk << " ret = " << ret << "\n";
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        for(int i = 0; i < 15; i++) {
            for(int j = 0; j < 15; j++) {
                dist[i][j] = 1e9;
            }
        }

        map<pair<int,int>,int> mp;
        vector<pair<int,int>> bv;

        cin >> h >> w;
        x_sz = 0;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> grid[i][j];
                if(grid[i][j] == 'X') {
                    mp[{i,j}] = x_sz++;
                }
                else if(grid[i][j] == 'B') {
                    bv.push_back({i,j});
                }
            }
        }
        for(int i = 0; i < bv.size(); i++) {
            bool vis[40][40] = {0};
            queue<pair<pair<int,int>,int>> q;
            vis[bv[i].first][bv[i].second] = 1;
            q.push({bv[i],0});
            while(!q.empty()) {
                pair<pair<int,int>,int> curr = q.front();
                q.pop();
                int r = curr.first.first;
                int c = curr.first.second;
                int w = curr.second;

                for(int j = 0; j < 4; j++) {
                    int x = r+dx[j];
                    int y = c+dy[j];
                    if(valid(x,y) && !vis[x][y]) {
                        //cout << "here2\n";
                        q.push({{x,y},w+1});
                        vis[x][y] = 1;
                        if(grid[x][y] == 'X') {
                            //cout << "here at mp[{x,y}] = " << mp[{x,y}] << " i = " << i << "\n";
                            dist[mp[{x,y}]][i] = w+1;
                        }
                    }
                }
            }
        }
        for(int i = 0; i < x_sz; i++) {
            for(int j = 0; j < 32799; j++) {
                mem[i][j] = -1;
            }
        }
        cout << solve(0,0) << "\n";
    }
    return 0;
}