Google Code Jam Japan 2011 本戦 D. クローゼットルーム(small)

D : クローゼットルーム

smallは全探索っぽいし時間余ったらやろうと思ったまま忘れ去られた問題

1つの点からタンスの置き方4通り + 置かない1通りを試す
壁や他のタンスと重なったり、ドアが塞がったらその置き方は諦める
という感じで、DFSしていけば良い

書いてみたコード

C++版

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int H, W; 
string mp[4];
bool door[4][4];
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

int solveSmall(int pos, int sx, int sy){
    if(pos == W*H) return 0;
    int res = solveSmall(pos+1, sx, sy);
    int x = pos/W, y = pos%W;
    for(int i=0;i<4;i++){
        if(isalpha(mp[x][y])) continue;
        int cx = x+dx[i],       cy = y+dy[i];
        int xx = x+dx[(i+1)%4], xy = y+dy[(i+1)%4];
        if(cx<0||H<=cx||cy<0||W<=cy||isalpha(mp[cx][cy])) continue;
        if(xx<0||H<=xx||xy<0||W<=xy||mp[xx][xy]=='X') continue;
        mp[x][y] = mp[cx][cy] = 'X';
        bool prev = door[xx][xy];
        door[xx][xy] = true;

        bool visit[4][4];
        memset(visit, false, sizeof(visit));
        queue< pair<int, int> > qu; qu.push(make_pair(sx, sy));
        while(!qu.empty()){
            pair<int,int> pr = qu.front(); qu.pop();
            int px = pr.first, py = pr.second;
            if(visit[px][py]) continue;
            visit[px][py] = true;
            for(int j=0;j<4;j++){
                int nx = px+dx[j], ny = py+dy[j];
                if(nx<0||H<=nx||ny<0||W<=ny||mp[nx][ny]=='X') continue;
                qu.push(make_pair(nx,ny));
            }
        }

        bool ok = true;
        for(int j=0;j<H;j++)
            for(int k=0;k<W;k++)
                if(door[j][k]&&!visit[j][k]) ok = false;
        if(ok) res = max(res, 1+solveSmall(pos+1, sx, sy));    

        door[xx][xy] = prev;
        mp[x][y] = mp[cx][cy] = '.';
    }
    return res;
}

int main(){
    int TEST; cin >> TEST;
    for(int test=1;test<=TEST;test++){
        cin >> H >> W;
        for(int i=0;i<H;i++) cin >> mp[i];
        int sx = 0, sy = 0;
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++)
                if(mp[i][j]=='D') sx = i, sy = j;
        memset(door, false, sizeof(door));
        printf("Case #%d: %d\n", test, solveSmall(0, sx, sy));
    }
}