一道毒瘤题
首先是最朴素的dfs，没有任何优化
#include<bits/stdc++.h>
using namespace std;
int a[5],b[5],c1,c2;
int p[5][5];
bool vis;
void dfs(int x,int y){
if(vis)return ;
if(y==1 && a[x-1]!=0)return ;
if(x==4 && b[y-1]!=0)return ;
if(x==4 && y==2 && c2!=0)return ;
if(x==5 && y==1){
if(c1!=0)return ;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++)printf("%d ",p[i][j]);
puts("");
}
vis=1;
return ;
}
if(p[x][y]){
if(y==4)dfs(x+1,1);
else dfs(x,y+1);
return ;
}
for(int i=1;i<=a[x] && i<=b[y];i++){
if(x==y && i>c1)break;
if(x+y==5 && i>c2)break;
a[x]-=i;b[y]-=i;
if(x==y)c1-=i;if(x+y==5)c2-=i;
p[x][y]=i;
if(y==4)dfs(x+1,1);
else dfs(x,y+1);
p[x][y]=0;
a[x]+=i;b[y]+=i;
if(x==y)c1+=i;if(x+y==5)c2+=i;
}
}
int main(){
for(int i=1;i<=4;i++)scanf("%d",&a[i]);
for(int i=1;i<=4;i++)scanf("%d",&b[i]);
scanf("%d%d",&c1,&c2);
for(int i=1;i<=4;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);x++;y++;
p[x][y]=z;
a[x]-=z;b[y]-=z;
if(x==y)c1-=z;
if(x+y==5)c2-=z;
}
dfs(1,1);
return 0;
}
可以得到48pts(开O2)
(加了个小优化：就是每行剩下没填的至少留1，但似乎没用)
优化1：如果现在搜的是该行、列、对角线的最后一个，那么直接填
#include<bits/stdc++.h>
using namespace std;
int a[5],b[5],c1,c2;
int p[5][5];
bool vis;
int la[7]={0,4,4,4,4},lb[7]={0,4,4,4,4},lc1=4,lc2=4;
inline bool check(int x,int y){
if(a[x]-la[x]<0)return 1;
if(b[y]-lb[y]<0)return 1;
if(c1<0 || c2<0)return 1;
return 0;
}
void dfs(int x,int y){
if(vis)return ;
if(y==1 && a[x-1]!=0)return ;
if(x==4 && b[y-1]!=0)return ;
if(x==4 && y==2 && c2!=0)return ;
if(check(x,y))return ;
if(x==5 && y==1){
if(c1!=0)return ;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++)
printf("%d ",p[i][j]);
puts("");
}
vis=1;
return ;
}
if(p[x][y]){
if(y==4)dfs(x+1,1);
else dfs(x,y+1);
return ;
}
int minn=1,maxx=max(a[x],b[y]);
if(la[x]==1)minn=maxx=a[x];
else if(lb[y]==1)minn=maxx=b[y];
else if(lc1==1)minn=maxx=c1;
else if(lc2==1)minn=maxx=c2;
for(int i=minn;i<=maxx && i<=a[x] && i<=b[y] && i>=1;i++){
if(x==y && i>c1)break;
if(x+y==5 && i>c2)break;
a[x]-=i;b[y]-=i;la[x]--;lb[y]--;
if(x==y)c1-=i,lc1--;if(x+y==5)c2-=i,lc2--;
p[x][y]=i;
if(y==4)dfs(x+1,1);
else dfs(x,y+1);
p[x][y]=0;
a[x]+=i;b[y]+=i;la[x]++;lb[y]++;
if(x==y)c1+=i,lc1--;if(x+y==5)c2+=i,lc2--;
}
}
int main(){
for(int i=1;i<=4;i++)scanf("%d",&a[i]);
for(int i=1;i<=4;i++)scanf("%d",&b[i]);
scanf("%d%d",&c1,&c2);
for(int i=1;i<=4;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);x++;y++;
p[x][y]=z;
a[x]-=z;b[y]-=z;la[x]--;lb[y]--;
if(x==y)c1-=z,lc1--;
if(x+y==5)c2-=z,lc2--;
}
dfs(1,1);
return 0;
}
得到68pts