信息学奥赛一本通T1446：素数方阵

【题目描述】

CE数码公司开发了一种名为自动涂色机（APM）的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。

为了涂色，APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子，并给所有颜色为C且符合下面限制的矩形涂色：

为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它上方的矩形涂色后，才能涂色。例如图中矩形F必须在C和D涂色后才能涂色。注意，每一个矩形必须立刻涂满，不能只涂一部分。

写一个程序求一个使APM拿起刷子次数最少的涂色方案。注意，如果一把刷子被拿起超过一次，则每一次都必须记入总数中。

【输入】

第一行为矩形的个数N。下面有N行描述了N个矩形。每个矩形有5个整数描述，左上角的y坐标和x坐标，右下角的y坐标和x坐标，以及预定颜色。

颜色号为1到20的整数。

平板的左上角坐标总是(0, 0)。

坐标的范围是0..99。N小于16。

【输出】

拿起刷子的最少次数。

【输入样例】

7 
0 0 2 2 1 
0 2 1 6 2 
2 0 4 2 1 
1 2 4 4 2 
1 4 3 6 1 
4 0 6 4 1 
3 4 6 6 2

【输出样例】

3

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int n,m;
int bit[6];
bool bprime[100000];
int G[500000][15];
bool vis[500000][10];
int judge[20000][10],tot;
int res[100];

int suf[6];
int sumX[6], sumY[6];
int sum[6];

void build(){//建图
    int x=0;
    for(int i=1;i<=5;i++){
        if(!vis[x][bit[i]]){
            G[x][0]++;
            G[x][G[x][0]]=bit[i];
            vis[x][bit[i]]=true;
        }
        x=((x<<4)|bit[i]);
    }

    x=0;
    for(int i=5;i>=1;i--){
        if(!judge[x][bit[i]])
            judge[x][bit[i]]=++tot;
        x=judge[x][bit[i]];
    }
}

void dfs(int x,int y) {
    if(x==6){
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                int pos=((i-1)<<3)|j;
                printf("%d",res[pos]);
            }
            printf("\n");
        }
        printf("\n");
    }
    else {
        int minn;
        if(G[sumX[x]][0]>G[sumY[y]][0])
            minn=sumY[y];
        else
            minn=sumX[x];
        for(int i=1;i<=G[minn][0];i++){
            int pos=res[((x - 1) << 3) | y] = G[minn][i];

            int flag1,flag2;
            if(x+y!=6)
                flag1=true;
            else{
                flag1=judge[suf[x-1]][pos];
                suf[x]=judge[suf[x-1]][pos];
            }
            if(x!=y)
                flag2=true;
            else{
                flag2=vis[sum[x-1]][pos];
                sum[x]=((sum[x-1]<<4)|pos);
            }

            if(!flag1||!flag2||!vis[sumY[y]][pos]||!vis[sumX[x]][pos])//存在性剪枝
                continue;

            sumX[x]=((sumX[x]<<4)|pos);
            sumY[y]=((sumY[y]<<4)|pos);

            if(y<5)
                dfs(x,y+1);
            else
                dfs(x+1,1);

            sumX[x]>>=4;
            sumY[y]>>=4;
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=3;i<=99999;i+=2){//判素数
        if(!bprime[i]){
            if(i>=10000){//分解数位
                bit[1]=i/10000;
                bit[2]=i/1000%10;
                bit[3]=i/100%10;
                bit[4]=i/10%10;
                bit[5]=i%10;
                if(bit[1]+bit[2]+bit[3]+bit[4]+bit[5]==n)//各数位和等于素数
                    build();//建图
            }
            for(int j=i*3;j<=99999;j+=2*i)
                bprime[j]=true;
        }
    }
    sum[1]=m;
    sumX[1]=m;
    sumY[1]=m;
    res[1]=m;
    dfs(1,2);
    return 0;
}

信息学奥赛一本通T1446：深搜的剪枝技巧 素数方阵 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 素数方阵