拼字游戏题解

· · 题解

拼字游戏题解

题目大意

要求得出一个 4 x 4 的矩形，使得它满足几个限制条件。

值域 \leq 300

算法1

首先矩形那么小，多半是搜索，所以考虑最暴力的方式：依次搜索每个格子的值，如果不符合题意就继续。但是这可能只有个位数的成绩。

最朴素的想法就是可行性剪枝，一边搜索一边判断已经结束的行或者列或者对角线的合法性，同时保证每个时刻，任何格子确定值了以后不会出现明显的导致行之和超过给定值的情况。

这样，通过最基础的算法，可以得到 24 分。

lin: 每一行当前的和
col: 每一列当前的和
cr1: 正对角线当前的和
cr2: 反对角线当前的和
val: 就是填出的矩阵

update: 搜索更新各个和

代码：

int val[5][5],lin[5],col[5],cr1,cr2;
void update(int x,int y,int v){
    lin[x]+=v,col[y]+=v;
    if(x==y) cr1+=v;
    if(x+y==5) cr2+=v;
}
void dfs(int x,int y){
    if(x==4&&y==5){
        if(cr1) return;
     if(col[4]) return; // 最后两个判断非常重要
        for(int i=1;i<=4;++i){
            for(int j=1;j<=4;++j)
                cout<<val[i][j]<<" ";
            cout<<endl;
        }
        exit(0);
    }
    if(y==5){
        if(lin[x]) return;
        dfs(x+1,1);
        return;
    }
    if(x==4&&y>1&&cr2) return;
    if(x==4&&col[y-1]!=0) return;
    if(val[x][y]){
        dfs(x,y+1);
        return;
    }
    int mx=min(lin[x],col[y]);
    if(x==y) mx=min(mx,cr1);
    if(x+y==5) mx=min(mx,cr2); // 计算最大可行值
    if(y==4){
        if(lin[x]==0) return;
        val[x][y]=lin[x],update(x,y,-val[x][y]);
        dfs(x,y+1);
        update(x,y,val[x][y]),val[x][y]=0;
        return;
    }
    for(int i=1;i<=mx;++i)
        update(x,y,-1),val[x][y]=i,dfs(x,y+1);
    val[x][y]=0,update(x,y,mx);
}
int main(){
    for(int i=1;i<=4;++i) cin>>lin[i];
    for(int i=1;i<=4;++i) cin>>col[i];
    cin>>cr1>>cr2;
    for(int i=1,x,y,v;i<=4;++i)
        cin>>x>>y>>v,++x,++y,val[x][y]=v,update(x,y,-v);
    dfs(1,1);
    return 0;
}

算法2

算法1浪费在无法在合适的时候解决掉一些不合法的状态。从上面的代码可以看到，列的和以及对角线和直到最后一行才被判断。同时，最大可行值也需要考虑给别的空格至少留下 1。

优化方案：记录每一时刻每行每列每对角线没有填的格子的数量。同时一些小小的常数优化，分数就变成了 78 分。

numl: 每行剩余空格数
numc: 每列剩余空格数
num1: 正对角线空格数
num2: 反对角线空格数

calc: 更新空格数
check: 判断一个格子填某个值是否合法
limit: 求一个格子当前最大可以填几

代码：

void calc(int x,int y,int v){
    numl[x]+=v,numc[y]+=v;
    if(x==y) num1+=v;
    if(x+y==5) num2+=v;
}
bool check(int x,int y,int v){
    if(v<=0) return 0;
    if(lin[x]<v+numl[x]-1) return 0;
    if(col[y]<v+numc[y]-1) return 0;
    if(x==y&&cr1<v+num1-1) return 0;
    if(x+y==5&&cr2<v+num2-1) return 0;
    return 1;
}
inline int limit(int x,int y){
    return min(min(lin[x]-numl[x],col[y]-numc[y]),min((x==y?cr1-num1:inf),(x+y==5?cr2-num2:inf)))+1;
}

特判只有一个剩余格子，其他以此类推。

if(numl[x]==1){
    if(!check(x,y,lin[x])) return;
    val[x][y]=lin[x],update(x,y,-val[x][y]),calc(x,y,-1);
    dfs(x,y+1);
    update(x,y,val[x][y]),calc(x,y,1),val[x][y]=0;
    return;
}

搜索该格的值。

int lmm=limit(x,y);
calc(x,y,-1);
for(int i=1;i<=lmm;++i)
    ++val[x][y],update(x,y,-1),dfs(x,y+1);
calc(x,y,1),val[x][y]=0,update(x,y,lmm);
// main 函数不要忘了一样要 calc

算法3

山重水复疑无路，柳暗花明又一村。

看似优化到底了，但是注意到这道题的目标是尽快找到一个合法的答案，而不是搜索所有的解。因此需要尽量使程序快速找到答案。

优化一：考虑到限制越大的格子先搜。先将所有格子按照最大可填值排序，依次按顺序搜索。

优化二：经过观察可以发现，如果一个格子填的值太大或者太小，那么找到解的概率会大致的随之下降。所以枚举一个格子的值可以从中间往后枚举，然后在枚举小的值。

通过这两个优化可以通过。

Tip: #48 数据占据总时间的 70%，不要被这数据点卡了！
sr: 排在第几的是哪个格子
dfs 的参数变为当前搜索的是第几个格子。

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int val[5][5],lin[5],col[5],cr1,cr2;
int numl[5],numc[5],num1,num2;
struct node{int x,y;} sr[35];
void update(int x,int y,int v){
    lin[x]+=v,col[y]+=v;
    if(x==y) cr1+=v;
    if(x+y==5) cr2+=v;
}
void calc(int x,int y,int v){
    numl[x]+=v,numc[y]+=v;
    if(x==y) num1+=v;
    if(x+y==5) num2+=v;
}
bool check(int x,int y,int v){
    if(v<=0) return 0;
    if(lin[x]<v+numl[x]-1) return 0;
    if(col[y]<v+numc[y]-1) return 0;
    if(x==y&&cr1<v+num1-1) return 0;
    if(x+y==5&&cr2<v+num2-1) return 0;
    return 1;
}
inline int limit(int x,int y){
    return min(min(lin[x]-numl[x],col[y]-numc[y]),min((x==y?cr1-num1:inf),(x+y==5?cr2-num2:inf)))+1;
}
inline bool cmp(const node&aa,const node&bb){
    return limit(aa.x,aa.y)<limit(bb.x,bb.y);
}
void dfs(int pos){
    int x=sr[pos].x,y=sr[pos].y;
    if(x==4&&y==5){
        for(int i=1;i<=4;++i)
            if(lin[i]) return;
        for(int i=1;i<=4;++i)
            if(col[i]) return;
        if(cr1||cr2) return;
        for(int i=1;i<=4;++i){
            for(int j=1;j<=4;++j)
                cout<<val[i][j]<<" ";
            cout<<endl;
        }
        exit(0);
    }
    if(numl[x]==1){
        if(!check(x,y,lin[x])) return;
        val[x][y]=lin[x],update(x,y,-val[x][y]),calc(x,y,-1);
        dfs(pos+1);
        update(x,y,val[x][y]),calc(x,y,1),val[x][y]=0;
        return;
    }
    if(numc[y]==1){
        if(!check(x,y,col[y])) return;
        val[x][y]=col[y],update(x,y,-val[x][y]),calc(x,y,-1);
        dfs(pos+1);
        update(x,y,val[x][y]),calc(x,y,1),val[x][y]=0;
        return;
    }
    if(num1==1&&x==y){
        if(!check(x,y,cr1)) return;
        val[x][y]=cr1,update(x,y,-val[x][y]),calc(x,y,-1);
        dfs(pos+1);
        update(x,y,val[x][y]),calc(x,y,1),val[x][y]=0;
        return;
    }
    if(num2==1&&x+y==5){
        if(!check(x,y,cr2)) return;
        val[x][y]=cr2,update(x,y,-val[x][y]),calc(x,y,-1);
        dfs(pos+1);
        update(x,y,val[x][y]),calc(x,y,1),val[x][y]=0;
        return;
    }
    int lmm=limit(x,y),l=lmm/3;
    l=max(l,1);
    calc(x,y,-1);
    update(x,y,-l+1);
    for(int i=l;i<=lmm;++i)
        val[x][y]=i,update(x,y,-1),dfs(pos+1);
    update(x,y,lmm);
    for(int i=1;i<l;++i)
        val[x][y]=i,update(x,y,-1),dfs(pos+1);
    calc(x,y,1),val[x][y]=0,update(x,y,l-1);
}
int main(){
    for(int i=1;i<=4;++i) cin>>lin[i],numl[i]=4;
    for(int i=1;i<=4;++i) cin>>col[i],numc[i]=4;
    cin>>cr1>>cr2,num1=num2=4;
    for(int i=1,x,y,v;i<=4;++i){
        cin>>x>>y>>v,++x,++y;
        val[x][y]=v,update(x,y,-v),calc(x,y,-1);
    }
    int tt=0;
    for(int i=1;i<=4;++i)
        for(int j=1;j<=4;++j)
            if(!val[i][j]) sr[++tt]=(node){i,j};
    sort(sr+1,sr+tt+1,cmp);
    sr[++tt]=(node){4,5};
    dfs(1);
    return 0;
}

总结