2010-1129

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题目大意 ==

已知一些形状的俄罗斯方块，问是否能精确填充某一个尺寸的矩形，给出方案。

== 分析 ==

精确覆盖问题， Dancing Link 的典型题目类型。

题目的规模也可以用 int64 按位做普通的搜索。用这种方法时，需要特别小心判断一个形状能不能放下。

== 参考程序 ==

下面是使用 int64 普通的搜索：

{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector <int> VI;

vector<int> Ans[100];

bool finish;

const int MAXNODE = 11000;
const int MAXCOLUMN = 500;
const int MAXDEPTH = 100;

class DancingLink {
public:
    int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE], C[MAXNODE];
    int selection[MAXDEPTH];
    int column[MAXCOLUMN], rowNode[MAXCOLUMN], N[MAXCOLUMN], S[MAXCOLUMN];
    int H; // Dancing Link head
    int ccNode; // the number of node in Dancing Link Table
    int columnSize; // the number of columns

    inline void init(int columnSize0) {
        H = 0;
        ccNode = 1;
        columnSize = columnSize0;
        for (int i = 1; i <= columnSize; i++) {
            column[i - 1] = C[i] = U[i] = D[i] = ccNode++;
            L[i] = R[i] = S[i] = 0;
            N[i] = i - 1;
        }
        // R
        R[H] = column[0];
        for (int i = 1; i < columnSize; i++) R[column[i - 1]] = column[i];
        R[column[columnSize - 1]] = H;
        // L
        L[H] = column[columnSize - 1];
        for (int i = columnSize - 1; i > 0; i--) L[column[i]] = column[i - 1];
        L[column[0]] = H;
    }

    inline void insertRow(int rowSize, int * row) { // the column index has sorted
        for (int i = 0; i < rowSize; i++) rowNode[i] = ccNode++;
        // R
        for (int i = 1; i < rowSize; i++) R[rowNode[i - 1]] = rowNode[i];
        R[rowNode[rowSize - 1]] = rowNode[0];
        // L
        for (int i = rowSize - 1; i > 0; i--) L[rowNode[i]] = rowNode[i - 1];
        L[rowNode[0]] = rowNode[rowSize - 1];
        // C U D
        for (int i = 0; i < rowSize; i++) {
            C[rowNode[i]] = column[row[i]];
            U[rowNode[i]] = U[column[row[i]]];
            D[rowNode[i]] = column[row[i]];
            D[U[rowNode[i]]] = U[D[rowNode[i]]] = rowNode[i];
            S[column[row[i]]]++;
        }
    }

    inline void coverColumn(int c) {
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i]) {
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                S[C[j]]--;
            }
        }
    }

    inline void uncoverColumn(int c) {
        for (int i = U[c]; i != c; i = U[i]) {
            for (int j = L[i]; j != i; j = L[j]) {
                S[C[j]]++;
                U[D[j]] = D[U[j]] = j;
            }
        }
        L[R[c]] = R[L[c]] = c;
    }

    inline void search(int depth) {
        if (R[H] == H) {
            for (int o = 0; o < depth; o++) {
                int j = selection[o];
                do {
                    Ans[o].push_back(N[C[j]]);
//                  printf("%d ", N[C[j]]);
                    j = R[j];
                } while (j != selection[o]);
//              puts("");
            }
            finish = true;
            return ;
        }
        // choose Column
        int mmins = 1000000000;
        int c;
        for (int j = R[H]; j != H; j = R[j]) {
            if (S[j] < mmins) {
                mmins = S[j];
                c = j;
            }
        }
        coverColumn(c);
        for (int r = D[c]; r != c; r = D[r]) {
            selection[depth] = r;
            for (int j = R[r]; j != r; j = R[j]) coverColumn(C[j]);
            search(depth + 1);
            if (finish) return;
            for (int j = L[r]; j != r; j = L[j]) uncoverColumn(C[j]);
        }
        uncoverColumn(c);
    }
} DL;

int N, x[100], y[100], shape[100][100][100];

int IND(int L, int W, int x, int y) {
    return y + x * W;
}

void get(int now, int &x, int &y, int L, int W) {
    y = now % W;
    x = now / W;
}

int v[100], ans[100][100];

void solve(int L, int W) {
    int columnsize = L * W + N;
    DL.init(columnsize);

    for (int i = 0; i < N; i++) Ans[i].clear();

    for (int i = 0; i < N; i++) {
        for (int x0 = 0; x0 + x[i] <= L; x0++)
            for (int y0 = 0; y0 + y[i] <= W; y0++) {
                int size = 0;
                for (int j = 0; j < x[i]; j++)
                    for (int k = 0; k < y[i]; k++)
                        if (shape[i][j][k]) { 
                            //v.push_back(IND(L, W, j + x0, k + y0));
                            v[size] = IND(L, W, j + x0, k + y0);
                            size++;
                        }
                v[size] = L * W + i;
                size++;
                DL.insertRow(size, v);
            }
    }
    DL.search(0);
    for (int i = 0; i < N; i++)
        sort(Ans[i].begin(), Ans[i].end());

    for (int i = 0; i < N; i++) {
        int color = Ans[i][(int)Ans[i].size() - 1] - L * W + 1;
        for (int j = 0; j < (int)Ans[i].size(); j++) {
            int x, y;
            get(Ans[i][j], x, y, L, W);
            ans[x][y] = color;
        }
    }

    if (finish) {
    printf("%d %d\n", L, W);
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < W - 1; j++) 
            printf("%d ", ans[i][j]);
        printf("%d\n", ans[i][W - 1]);
    }
    puts("");
    }
}

int main() {

    while (scanf("%d", &N) != EOF) {
        int area = 0, L = 0, W = 0;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &x[i], &y[i]);
            L = max(L, x[i]);
            W = max(W, y[i]);
            for (int j = 0; j < x[i]; j++)
                for (int k = 0; k < y[i]; k++) {
                    scanf("%d", &shape[i][j][k]);   
                    area += shape[i][j][k];
                }
        }   
        finish = false;
        for (int l = L; l * W <= area; l++) {
            if (area % l != 0) continue;
            int w = area / l;
            solve(l, w);
            if (finish) break;
        }
    }
    return 0;
}

}}}

题目大意

已知一些形状的俄罗斯方块，问是否能精确填充某一个尺寸的矩形，给出方案。

分析

精确覆盖问题， Dancing Link 的典型题目类型。

题目的规模也可以用 int64 按位做普通的搜索。用这种方法时，需要特别小心判断一个形状能不能放下。

参考程序

下面是使用 int64 普通的搜索：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector <int> VI;
vector<int> Ans[100];
bool finish;
const int MAXNODE = 11000;
const int MAXCOLUMN = 500;
const int MAXDEPTH = 100;
class DancingLink {
public:
    int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE], C[MAXNODE];
    int selection[MAXDEPTH];
    int column[MAXCOLUMN], rowNode[MAXCOLUMN], N[MAXCOLUMN], S[MAXCOLUMN];
    int H; // Dancing Link head
    int ccNode; // the number of node in Dancing Link Table
    int columnSize; // the number of columns
    inline void init(int columnSize0) {
        H = 0;
        ccNode = 1;
        columnSize = columnSize0;
        for (int i = 1; i <= columnSize; i++) {
            column[i - 1] = C[i] = U[i] = D[i] = ccNode++;
            L[i] = R[i] = S[i] = 0;
            N[i] = i - 1;
        }
        // R
        R[H] = column[0];
        for (int i = 1; i < columnSize; i++) R[column[i - 1]] = column[i];
        R[column[columnSize - 1]] = H;
        // L
        L[H] = column[columnSize - 1];
        for (int i = columnSize - 1; i > 0; i--) L[column[i]] = column[i - 1];
        L[column[0]] = H;
    }
    inline void insertRow(int rowSize, int * row) { // the column index has sorted
        for (int i = 0; i < rowSize; i++) rowNode[i] = ccNode++;
        // R
        for (int i = 1; i < rowSize; i++) R[rowNode[i - 1]] = rowNode[i];
        R[rowNode[rowSize - 1]] = rowNode[0];
        // L
        for (int i = rowSize - 1; i > 0; i--) L[rowNode[i]] = rowNode[i - 1];
        L[rowNode[0]] = rowNode[rowSize - 1];
        // C U D
        for (int i = 0; i < rowSize; i++) {
            C[rowNode[i]] = column[row[i]];
            U[rowNode[i]] = U[column[row[i]]];
            D[rowNode[i]] = column[row[i]];
            D[U[rowNode[i]]] = U[D[rowNode[i]]] = rowNode[i];
            S[column[row[i]]]++;
        }
    }
    inline void coverColumn(int c) {
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i]) {
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                S[C[j]]--;
            }
        }
    }
    inline void uncoverColumn(int c) {
        for (int i = U[c]; i != c; i = U[i]) {
            for (int j = L[i]; j != i; j = L[j]) {
                S[C[j]]++;
                U[D[j]] = D[U[j]] = j;
            }
        }
        L[R[c]] = R[L[c]] = c;
    }
    inline void search(int depth) {
        if (R[H] == H) {
            for (int o = 0; o < depth; o++) {
                int j = selection[o];
                do {
                    Ans[o].push_back(N[C[j]]);
//                  printf("%d ", N[C[j]]);
                    j = R[j];
                } while (j != selection[o]);
//              puts("");
            }
            finish = true;
            return ;
        }
        // choose Column
        int mmins = 1000000000;
        int c;
        for (int j = R[H]; j != H; j = R[j]) {
            if (S[j] < mmins) {
                mmins = S[j];
                c = j;
            }
        }
        coverColumn(c);
        for (int r = D[c]; r != c; r = D[r]) {
            selection[depth] = r;
            for (int j = R[r]; j != r; j = R[j]) coverColumn(C[j]);
            search(depth + 1);
            if (finish) return;
            for (int j = L[r]; j != r; j = L[j]) uncoverColumn(C[j]);
        }
        uncoverColumn(c);
    }
} DL;
int N, x[100], y[100], shape[100][100][100];
int IND(int L, int W, int x, int y) {
    return y + x * W;
}
void get(int now, int &x, int &y, int L, int W) {
    y = now % W;
    x = now / W;
}
int v[100], ans[100][100];
void solve(int L, int W) {
    int columnsize = L * W + N;
    DL.init(columnsize);
    for (int i = 0; i < N; i++) Ans[i].clear();
    for (int i = 0; i < N; i++) {
        for (int x0 = 0; x0 + x[i] <= L; x0++)
            for (int y0 = 0; y0 + y[i] <= W; y0++) {
                int size = 0;
                for (int j = 0; j < x[i]; j++)
                    for (int k = 0; k < y[i]; k++)
                        if (shape[i][j][k]) { 
                            //v.push_back(IND(L, W, j + x0, k + y0));
                            v[size] = IND(L, W, j + x0, k + y0);
                            size++;
                        }
                v[size] = L * W + i;
                size++;
                DL.insertRow(size, v);
            }
    }
    DL.search(0);
    for (int i = 0; i < N; i++)
        sort(Ans[i].begin(), Ans[i].end());
    for (int i = 0; i < N; i++) {
        int color = Ans[i][(int)Ans[i].size() - 1] - L * W + 1;
        for (int j = 0; j < (int)Ans[i].size(); j++) {
            int x, y;
            get(Ans[i][j], x, y, L, W);
            ans[x][y] = color;
        }
    }
    if (finish) {
    printf("%d %d\n", L, W);
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < W - 1; j++) 
            printf("%d ", ans[i][j]);
        printf("%d\n", ans[i][W - 1]);
    }
    puts("");
    }
}
int main() {
    while (scanf("%d", &N) != EOF) {
        int area = 0, L = 0, W = 0;
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &x[i], &y[i]);
            L = max(L, x[i]);
            W = max(W, y[i]);
            for (int j = 0; j < x[i]; j++)
                for (int k = 0; k < y[i]; k++) {
                    scanf("%d", &shape[i][j][k]);   
                    area += shape[i][j][k];
                }
        }   
        finish = false;
        for (int l = L; l * W <= area; l++) {
            if (area % l != 0) continue;
            int w = area / l;
            solve(l, w);
            if (finish) break;
        }
    }
    return 0;
}