Problem 1140 : Cleaning Robot

keyword

最短経路　BFS　BruteForce　C++

概要

地図とゴミの位置とロボットの初期位置が与えられる。ロボットがゴミを拾うのに最短で歩く距離を求める問題。ゴミの位置は10以下。地図は20*20以下。
前処理として各ゴミと初期位置間の距離をBFSとかで計算しておけば後は10!通り全探索すればよい。ただしこの方法だとAOJでは通ったがPKUではTLE。一応座標を一つのintで持つとか細かい最適化はしたのですが、それ以上の枝刈りなどが必要かもしれません。

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

inline int PtoN(int x, int y){
    return 20*x + y;
}

int main(){
    int w, h, i, j, d, st, best, dd, cur;
    string line;
    while(scanf("%d%d\n",&w,&h)){
        if(!(w||h)) break;
        vector<string> board;
        vector< vector<int> > dist(400, vector<int>(400,1<<21));
        vector<int> ds;
        d = 0;
        REP(i,h){
            getline(cin,line);
            board.PB(line);
        }
        REP(i,h)REP(j,w){
            if(board[i][j]=='*'){
                d++;
                ds.PB(PtoN(j,i));
            }
            else if(board[i][j]=='o'){
                st = PtoN(j,i);
            }
        }
        sort(ALL(ds));
        ds.PB(st);
        REP(i,d+1){
            queue<int> Q;
            Q.push(1000*ds[i] + 0);
            while(!Q.empty()){
                int tp=Q.front();
                int cd = tp/1000, cx=cd/20, cy=cd%20, dss=tp%1000;
                REP(j,4){
                    int x=cx+dx[j], y=cy+dy[j];
                    if(0<=x && x<w && 0<=y && y<h &&
                            board[y][x]!='x' &&
                            dist[ds[i]][PtoN(x,y)]>(1<<20)){
                        Q.push(1000*PtoN(x,y)+dss+1);
                        dist[ds[i]][PtoN(x,y)] = dss+1;
                    }
                }
                Q.pop();
            }
        }
        ds.pop_back();
        best = 1<<21;
        do{
            dd = dist[st][ds[0]];
            REP(i,d-1){
                dd += dist[ds[i]][ds[i+1]];
                if(dd >= best) goto end;
            }
            best = dd;
end:;
        }while(next_permutation(ALL(ds)));
        printf("%d\n",(best>(1<<20))?-1:best);
    }
    return 0;
}