P3969 [TJOI2014]拼图题解

seac_blue · 2021-10-15 09:35:53 · 题解

主要算法是搜索，注意实现细节。

思路

读入并处理每一块拼图
dfs 每一块拼图放在哪里

2.1. 判断能否放置
2.2. 如果能，将拼图对应的相对坐标覆盖到版面的绝对坐标上
2.3. 重复 2.
2.4. 回溯，将拼图对应的相对坐标从版面的绝对坐标抠出来

每次 bfs 判断是否覆盖满

3.1 开一个答案数组和答案个数记录
3.2 如果答案个数 =0\to No solution
3.3 如果答案个数 =1\to Yes, only one!
3.4 如果答案个数 =2\to Yes, many! 并且直接退出。

实现

步骤 1 使用结构体存储。

步骤 2.1 可以用一一对应的方式写个判断函数。

步骤 2.2 和 2.4 可以写个覆盖函数，参数稍作修改，不需要写两次。

步骤 3 需要写个判断是否填满的函数。

总体框架见上，依旧注意实现细节。

（感觉这题难度标高了，建议绿）

代码

代码省略了头文件和快读。变量和函数都写有一定的注释解释。

using namespace std;
typedef long long ll;

ll read(){/* 快读 */}
ll reads(){/* 读入一个数字 0/1 */}

ll n;
ll f[5][5];// 操作版面
ll restime;// 答案个数
ll res[5][5];// 答案版面
bool allret;// 如果 allret=true 那么 dfs() 全部返回

struct Puzzle{
    ll w,h;
    bool p[5][5];
}a[20];

bool allFill(){// 版面是否填满
    for(ll i=1;i<=4;++i){
        for(ll j=1;j<=4;++j){
            if(!f[i][j])return false;
        }
    }
    return true;
}
bool check(ll id,ll x,ll y){// 是否可以以 (x,y) 为左上角放置拼图 id
    for(ll i=1;i<=a[id].w;++i){
        for(ll j=1;j<=a[id].h;++j){
            if(!a[id].p[i][j])continue;
            ll px=x+i-1,py=y+j-1;
            if(px>4 || py>4)return false;
            if(f[px][py])return false;
        }
    }
    return true;
}
void set(ll id,ll x,ll y,ll fillOper){// 以 (x,y) 为左上角放置 id
    for(ll i=1;i<=a[id].w;++i){
        for(ll j=1;j<=a[id].h;++j){
            if(!a[id].p[i][j])continue;
            ll px=x+i-1,py=y+j-1;
            f[px][py]=fillOper;
        }
    }
}

void dfs(ll k){
    bool p=allFill();
    if(p || k>n){// 边界条件
        if(p){// 版面填满
            if(restime){
                allret=true;
                restime=2;
                return;
            }else{
                restime=1;
                for(ll i=1;i<=4;++i){
                    for(ll j=1;j<=4;++j){
                        res[i][j]=f[i][j];
                    }
                }
                return;
            }
        }
        return;
    }
    for(ll i=1;i<=4;++i){
        for(ll j=1;j<=4;++j){
            if(check(k,i,j)){
                set(k,i,j,k);
                dfs(k+1);
                if(allret)return;
                set(k,i,j,0);
            }
        }
    }
    dfs(k+1);// 选择不要这块拼图，但是似乎所有拼图都会用上……？
}

int main(){
    while(scanf("%lld\n",&n)!=EOF){
        for(ll i=1;i<=n;++i){
            a[i].w=read();a[i].h=read();
            for(ll j=1;j<=a[i].w;++j){
                for(ll k=1;k<=a[i].h;++k){
                    a[i].p[j][k]=reads();
                }
            }
        }
        allret=false;restime=0;
        for(ll i=1;i<=4;++i){
            for(ll j=1;j<=4;++j){
                f[i][j]=0;
            }
        }
        dfs(1);
        if(restime==2){
            printf("Yes, many!\n");
        }if(restime==0){
            printf("No solution\n");
        }if(restime==1){
            printf("Yes, only one!\n");
            for(ll i=1;i<=4;++i,putchar('\n')){
                for(ll j=1;j<=4;++j){
                    printf("%lld",res[i][j]);
                }
            }
        }
    }
    return 0;
}

P3969 [TJOI2014]拼图 题解

思路

实现

代码

P3969 [TJOI2014]拼图题解