SRM-425 500pt: PiecesMover

keyword

幅優先探索　C++

問題概要

サイズ5*5のボードが与えられ、そのうちN(<=5)マスには荷物が置いてある。全ての荷物を連結させるとき、最小で何回の移動が必要か求める問題。

解法

全状態が(25,5)通りしかないので探索が間に合う。書くだけ。

感想

最初はN(<5)の条件を見落としていたので最大ケース(25,13)だと思っていた。以下のソースでビット演算使っているのはその名残りだけど、N<=5でないと25倍が響いてどうせTLEするとおもう。ちなみに、N<=5という条件は非常に緩いので、多分ビット演算なんて細かいことはせずに2次元のvector突っ込んでも間に合うと思う。あと相変わらず実装が遅すぎる。

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N, C;
int brd[5][5];

int getMinimumMoves(vector <string> board) {
    set<int> visited;
    int i, j, bit=0, k;
    N = 0;
    REP(i,5)REP(j,5)if(board[i][j] == '*'){
        N++;
        bit |= 1<<(i*5+j);
    }
    visited.insert(bit);
    queue< pair<int,int> > Q;
    Q.push( MP(bit, 0) );
    while(!Q.empty()){
        bit = Q.front().first;
        int d = Q.front().second; Q.pop();
        if(isConnect(bit)){
            return d;
        }
        REP(i,5)REP(j,5)if((bit>>(i*5+j))&1){
            int t = bit;
            REP(k,4){
                t = bit^(1<<(i*5+j));
                int ny = i+dy[k], nx = j + dx[k];
                if(0<=ny&&ny<5 && 0<=nx&&nx<5 && !((t>>(ny*5+nx))&1)){
                    t ^= 1<<(ny*5+nx);
                    if(visited.find(t) == visited.end()){
                        visited.insert(t);
                        Q.push( MP(t, d+1) );
                    }
                }
            }
        }
    }
    return -1;
}

inline bool isConnect(int bbit){
    int i, j;
    REP(i,5)REP(j,5)brd[i][j] = ((bbit>>(i*5+j))&1)?1:0;
    C = 0;
    REP(i,5)REP(j,5)if(brd[i][j]==1){ dfs(i,j); return C == N; }
}

inline void dfs(int y, int x){
    int k;
    C++;
    brd[y][x] = 0;
    REP(k,4){
        int ny = y + dy[k], nx = x + dx[k];
        if(0<=ny&&ny<5&&0<=nx&&nx<5 && brd[ny][nx])
            dfs(ny,nx);
    }
}