不对找我
2025-03-24 21:24:01
发布于:山西
#include<bits/stdc++.h>
using namespace std;
int n,m,p,L[205],R[205],a[205][205],b[205][205],c[205][205];//a是给我们的,b是预处理出来的,c是答案,L、R用来存储范围
void dfs(int j){
if(j==m+1){//搜索完了
for(int i=2;i<=n;i++){
for(int j=2;j<=m;j++){
c[i][j]=a[i][j]-c[i-1][j]-c[i][j-1]-c[i-1][j-1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",c[i][j]);
}
puts("");
}//输出
exit(0);//结束
}
int l[205],r[205];
for(int i=2;i<=n;i++)l[i]=L[i],r[i]=R[i];//把范围先存下来
for(int k=0;k<p;k++){//枚举值
c[1][j]=k;//更新答案
bool flag=1;
if(j>1){
for(int i=2;i<=n&&flag;i++){
c[i][j]=b[i][j]+((i&1)?1:-1)*c[1][j]+(((j+i)&1)?1:-1)*c[1][1];
if(j&1){
if(c[i][j]>=p)flag=0;
else if(c[i][j]<0)L[i]=max(L[i],-c[i][j]);
else R[i]=min(R[i],p-c[i][j]-1);
}
else{
if(c[i][j]<0)flag=0;
else if(c[i][j]>=p)L[i]=max(L[i],c[i][j]+1-p);
else R[i]=min(R[i],c[i][j]);
}//更新范围
if(L[i]>R[i])flag=0;//不合法
c[i][1]=L[i];//合法,贪心的选择
}
}
if(flag)dfs(j+1);//是合法的,递归
for(int i=2;i<=n;i++)L[i]=l[i],R[i]=r[i];//否则回溯
}
}
signed main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i=2;i<=n;i++)L[i]=0,R[i]=p-1;//范围的处理
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)b[i][j]=a[i][j]-b[i-1][j]-b[i][j-1]-b[i-1][j-1];//预处理b
dfs(1);//搜索
return 0;
}
这里空空如也
有帮助,赞一个