AOJ 1128 Square Carpets

AOJ 探索

問題

w x hのグリッドであらわされる部屋がある。
部屋の各マスは0（ふつうのマス）または1（破損したマス）のどちらかである。
今、正方形のカーペットを何枚か敷いて、0のマスは一切覆わずに1のマスを全て覆いたい。


カーペットは好きな大きさのものを何枚でも使え、重ねることもできるが、
グリッドの外へはみだしてはならない。


最低で何枚のカーペットを使えば1のマスを全て覆えるか、求めよ。

制約条件

w, h ≦ 15

方針

カーペットの敷き方のうち、3辺が0のマスまたはグリッドの外と接していないような敷き方は考えなくてよい。
（より大きな敷き方に完全に含まれるため）
このような敷き方の列挙は、計算量のクリティカルな部分ではないので、適当にやっても大丈夫。
自分は適当にDPをした。


カーペットの敷き方を全列挙したら、探索する。
探索はIDDFS（反復深化深さ優先探索）をした。

ソースコード

#include<stdio.h>
 
int w, h, p[15][15], dp[16][16], limit;
int rect[300][3], n, r[15][15][100], sz[15][15];
 
int rec(int y, int x, int m){
    int i, j, k, Y, X, len, bkup[15][15];
    if(x >= w) return rec(y+1, 0, m);
    if(y >= h) return 1;
    if(p[y][x] == 1){
        if(m >= limit) return 0;
        for(i = 0; i < sz[y][x]; i++){
            Y = rect[r[y][x][i]][0];
            X = rect[r[y][x][i]][1];
            len = rect[r[y][x][i]][2];
            for(j = 0; j < len; j++) for(k = 0; k < len; k++)
                bkup[j][k] = p[Y+j][X+k], p[Y+j][X+k] = 2;
            if(rec(y, x+1, m+1)) return 1;
            for(j = 0; j < len; j++) for(k = 0; k < len; k++)
                p[Y+j][X+k] = bkup[j][k];
        }
        return 0;
    }
    return rec(y, x+1, m);
}
 
int main(){
    int i, j, k, l, Y, X, len, ans;
    while(scanf("%d%d", &w, &h), w){
        for(i = 0; i < h; i++) for(j = 0; j < w; j++)
            scanf("%d", p[i]+j), sz[i][j] = 0;
        for(i = 0; i <= h; i++) for(j = 0; j <= w; j++) dp[i][j] = 0;
         
        for(i = h-1; i >= 0; i--) for(j = w-1; j >= 0; j--){
            if(p[i][j]){
                dp[i][j] = dp[i+1][j];
                if(dp[i][j] > dp[i][j+1]) dp[i][j] = dp[i][j+1];
                if(dp[i][j] > dp[i+1][j+1]) dp[i][j] = dp[i+1][j+1];
                dp[i][j]++;
            }
        }
        n = ans = 0;
        for(i = 0; i < h; i++) for(j = 0; j < w; j++){
            X = i == 0 || j == 0;
            if(!X){
                Y = dp[i-1][j]-1;
                if(Y < dp[i][j-1]-1) Y = dp[i][j-1]-1;
                if(Y < dp[i-1][j-1]-1) Y = dp[i-1][j-1]-1;
                if(Y < dp[i][j]) X = 1;
            }
            if(X){
                rect[n][0] = i; rect[n][1] = j; rect[n][2] = dp[i][j];
                for(k = 0; k < dp[i][j]; k++) for(l = 0; l < dp[i][j]; l++)
                    r[i+k][j+l][sz[i+k][j+l]++] = n;
                n++;
            }
        }
        for(i = 0; i < h; i++) for(j = 0; j < w; j++) if(sz[i][j] == 1 && p[i][j] == 1){
            ans++;
            Y = rect[r[i][j][0]][0];
            X = rect[r[i][j][0]][1];
            len = rect[r[i][j][0]][2];
            for(k = 0; k < len; k++) for(l = 0; l < len; l++) p[Y+k][X+l] = 2;
        }
         
        for(limit = 0; ; limit++){
            if(rec(0, 0, 0)){
                printf("%d\n", ans + limit); break;
            }
        }
    }
    return 0;
}