ICPC 国内予選2005F Cleaning Robot AOJ 1140

解法：ロボットとそれぞれの汚れたタイル間の距離を幅優先探索で求める。
この時点でロボットから到達できない汚れたタイルがあるかどうかわかるので-1の出力判定ができる。
あとはnext_permutationですべての汚れたタイルを回る順番を全通りためしてその中の最小値を求めればよい。（計算量は高々10!であるから余裕）

個人的には難易度350ぐらいかそれより簡単に感じた。（JOIer補正がかかっているのかもしれないが、、、
解法は自明であるので実装が重いから難易度が高くなっているのかもしれない

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int d[12][12];
int place[12][2];

int main(){
    int w,h,m[25][25];
    while(true){
        cin >> w >> h;
        int dirt = 0;
        if(w == 0 && h == 0)break;
        for(int i = 0;i < 11;i++){
            for(int j = 0;j < 11;j++){
                d[i][j] = -1;
            }
        }
        for(int i = 0;i < h;i++){
            char tmp[25];
            cin >> tmp;
            for(int j = 0;j < w;j++){
                if(tmp[j] == 'o'){
                    m[i][j] = 0;
                    place[0][0] = i; place[0][1] = j;
                }else if(tmp[j] == 'x'){
                    m[i][j] = -2;
                }else if(tmp[j] == '*'){
                    dirt++;
                    m[i][j] = dirt;
                    place[dirt][0] = i; place[dirt][1] = j;
                }else{
                    m[i][j] = -1;
                }
            }
        }
        for(int i = 0;i <= dirt;i++){
            int flag[25][25];
            bool ch[25][25];
            for(int i = 0;i < 22;i++){ //init
                for(int j = 0;j < 22;j++){
                    flag[i][j] = -1;
                    ch[i][j] = false;
                }
            }
            flag[place[i][0]][place[i][1]] = 0;
            queue<P> que;
            int count = 0;
            que.push(P(place[i][0],place[i][1]));
            ch[place[i][0]][place[i][1]] = true;
            while(!que.empty()){
                P q = que.front(); que.pop();
           //     if(ch[q.fs][q.sc] == true)continue;
           //     ch[q.fs][q.sc] = true;
                int num = m[q.fs][q.sc];
                if(num >= 0 && num != i){
                    d[i][num] = flag[q.fs][q.sc];
                    count++;
                    if(count == dirt) break;               
                }
                for(int i = 0;i < 4;i++){
                    int ni = q.fs+dx[i],nj = q.sc+dy[i];
                    if(ni >= 0 && ni < h && nj >= 0 && nj < w && ch[ni][nj] == false && m[ni][nj] >= -1){
                        ch[ni][nj] = true;
                        flag[ni][nj] = flag[q.fs][q.sc] + 1;
                        que.push(P(ni,nj));
                    }
                }
            }
        }
/* 
        for(int i = 0;i <= dirt;i++){
            for(int j = 0;j <= dirt;j++){
                cout << d[i][j] << " ";
            }
            cout << endl;
        }
*/
        int ans = 0;
        for(int i = 1;i <= dirt;i++){
            if(d[0][i] == -1){
                ans = -1;
            }
        }
        if(ans == -1){
            cout << -1 << endl;
            continue;
        }
        vector<int> vec;
        ans = 10000000;
        for(int i = 1;i <= dirt;i++){
            vec.push_back(i);
        }
        do{
            int tmpans = d[0][vec[0]];
            for(int i = 0;i < dirt-1;i++){
                tmpans += d[vec[i]][vec[i+1]];
            }
            if(ans > tmpans) ans = tmpans;
        }while(next_permutation(vec.begin(),vec.end()));
        cout << ans << endl;
    }
}