NC54281. GJX的Matrix
描述
1 2 3
4 5 6
GJX非常开心，在纸上写下很多“等差矩阵”。GJX想，如果给你一个部分位置数字缺失的3×3“等差矩阵”，你能否将矩阵还原呢？
输入描述
第一行一个数字Q，表示样例组数。Q<200
紧接着3*Q行，每3行一个3X3矩阵，
每行3个元素，整数或者’?’,’?’表示该位置数字缺失。
输入矩阵中已经给定的整数的绝对值不超过1e7。
输入保证有解。
输出描述
对于每个测试样例，输出还原后的矩阵。
还原后矩阵中每个数字必须是整数，且所有数字绝对值不超过1e9。
若解不唯一，输出任意一组。
示例1
输入:
2 1 2 3 4 ? 6 7 ? 9 -10 ? ? ? ? ? ? ? ?
输出:
1 2 3 4 5 6 7 8 9 -10 -10 -10 -10 -10 -10 -10 -10 -10
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 352K, 提交时间: 2019-10-26 20:30:01
#include<bits/stdc++.h>
#define int long long
using namespace std;
int A[3][3];
bool B[3][3];
void read()
{
string s;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
A[i][j]=B[i][j]=0;
cin>>s;
if(s!="?")
{
A[i][j]=0;
int n=s.length();
int k=0,p=1;
if(s[0]=='-')
{
k++;
p=-1;
}
for(k; k<n; k++)
{
A[i][j]=A[i][j]*10+(s[k]-'0');
}
A[i][j]*=p;
B[i][j]=1;
}
}
}
}
int cal()
{
int ans=0;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(B[i][j])ans++;
}
}
return ans;
}
void solve()
{
bool f=0;
while(true)
{
f=0;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(!B[i][j])
{
if(B[i][(j+1)%3]&&B[i][(j+2)%3])
{
f=1;
B[i][j]=1;
if(j==0) ///第一列
{
A[i][j]=2*A[i][j+1]-A[i][j+2];
}
else if(j==1) ///第二列
{
A[i][j]=(A[i][j-1]+A[i][j+1])/2;
}
else if(j==2) ///第三列
{
A[i][j]=2*A[i][j-1]-A[i][j-2];
}
}
}
}
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(!B[j][i])
{
if(B[(j+1)%3][i]&&B[(j+2)%3][i])
{
f=1;
B[j][i]=1;
if(j==0) ///第一行
{
A[j][i]=2*A[j+1][i]-A[j+2][i];
}
else if(j==1) ///第二行
{
A[j][i]=(A[j-1][i]+A[j+1][i])/2;
}
else if(j==2) ///第三行
{
A[j][i]=2*A[j-1][i]-A[j-2][i];
}
}
}
}
}
if(!f)break;///不能填了
}
}
void output()
{
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
cout<<A[i][j]<<(j==2?'\n':' ');
}
}
}
bool check_c(int i)///判断当前行是否满
{
for(int j=0; j<3; j++)
{
if(!B[i][j])return false;
}
return true;
}
bool check_r(int i)///判断当前列是否满
{
for(int j=0; j<3; j++)
{
if(!B[j][i])return false;
}
return true;
}
void work()
{
read();
solve();
int t=cal();
if(t==9||t==0)
{
output();
return;
}
else if(t==1) ///一个已知元素
{
int _x;
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(B[i][j])
{
_x=A[i][j];
break;
}
}
}
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
A[i][j]=_x;
}
}
output();
}
else if(t==2)
{
int a=-1,b,c,d;///记录两点位置
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(B[i][j]&&a==-1)
{
a=i,b=j;
}
else if(B[i][j])
{
c=i,d=j;
}
}
}
if(c-a==1)
{
for(int i=0; i<3; i++)
{
A[a][i]=A[a][b];
A[c][i]=A[c][d];
B[a][i]=B[c][i]=1;
}
}
else
{
for(int i=0; i<3; i++)
{
A[i][b]=A[a][b];
A[i][d]=A[c][d];
B[i][b]=B[i][d]=1;
}
}
solve();
output();
}
else if(t==3)
{
for(int i=0; i<3; i++)
{
if(check_c(i))
{
for(int j=0; j<3; j++)
{
for(int k=0; k<3; k++)
{
A[j][k]=A[i][k];
}
}
output();
return;
}
}
for(int i=0; i<3; i++)
{
if(check_r(i))
{
for(int j=0; j<3; j++)
{
for(int k=0; k<3; k++)
{
A[j][k]=A[j][i];
}
}
output();
return ;
}
}
if(B[1][1])
{
/**a X X
X b X
X X c*/
A[0][1]=0;
B[0][1]=1;
solve();
output();
}
else
{
/** X b X
a X X
X X c*/
A[1][1]=0;
B[1][1]=1;
solve();
output();
}
}
else if(t==5)
{
int a,b;
for(int i=0; i<3; i++)
{
if(check_c(i))
{
a=i;
}
if(check_r(i))
{
b=i;
}
}
A[(a+1)%3][(b+1)%3]=A[(a+1)%3][b]-A[a][b]+A[a][(b+1)%3];
B[(a+1)%3][(b+1)%3]=1;
solve();
output();
}
}
bool check()
{
for(int i=0;i<3;i++){
if(A[i][1]*2!=A[i][0]+A[i][2]){
return false;
}
if(A[1][i]*2!=A[0][i]+A[2][i]){
return false;
}
}
return true;
}
signed main()
{
int Q;
//freopen("1.in","r",stdin);
//freopen("1.out","w+",stdout);
scanf("%lld",&Q);
//int K=1,t=0;
while(Q--){
work();
}
//cout<<"T"<<t<<endl;
}
C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2022-12-10 23:40:29
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#include <assert.h>
const double eps=1e-8;
const ll inf=1e9;
const ll mod=1e9+7;
const int maxn=1e5+10;
struct node
{
int a[4][4];
}f,r;
int wrong=-2e9;
char str[100];
bool vis;
bool check(node f)
{
int i;
for (i=1;i<=3;i++)
if (f.a[i][1]!=wrong && f.a[i][2]!=wrong && f.a[i][3]!=wrong && f.a[i][2]*2!=f.a[i][1]+f.a[i][3])
return 0;
for (i=1;i<=3;i++)
if (f.a[1][i]!=wrong && f.a[2][i]!=wrong && f.a[3][i]!=wrong && f.a[2][i]*2!=f.a[1][i]+f.a[3][i])
return 0;
return 1;
}
bool complete(node f)
{
int i,j;
for (i=1;i<=3;i++)
for (j=1;j<=3;j++)
if (f.a[i][j]==wrong)
return 0;
return 1;
}
void print(node f)
{
int i,j;
for (i=1;i<=3;i++)
for (j=1;j<=3;j++)
printf("%d%c",f.a[i][j],j==3?'\n':' ');
}
bool add(node &f)
{
int i,j;
for (j=1;j<=10;j++) ///maybe can smaller
{
for (i=1;i<=3;i++)
{
if (f.a[i][1]==wrong && f.a[i][2]!=wrong && f.a[i][3]!=wrong)
f.a[i][1]=f.a[i][2]*2-f.a[i][3];
if (f.a[i][2]==wrong && f.a[i][1]!=wrong && f.a[i][3]!=wrong)
{
if ((f.a[i][1]+f.a[i][3])%2==1)
return 0;
f.a[i][2]=(f.a[i][1]+f.a[i][3])/2;
}
if (f.a[i][3]==wrong && f.a[i][1]!=wrong && f.a[i][2]!=wrong)
f.a[i][3]=f.a[i][2]*2-f.a[i][1];
}
for (i=1;i<=3;i++)
{
if (f.a[1][i]==wrong && f.a[2][i]!=wrong && f.a[3][i]!=wrong)
f.a[1][i]=f.a[2][i]*2-f.a[3][i];
if (f.a[2][i]==wrong && f.a[1][i]!=wrong && f.a[3][i]!=wrong)
{
if((f.a[1][i]+f.a[3][i])%2==1)
return 0;
f.a[2][i]=(f.a[1][i]+f.a[3][i])/2;
}
if (f.a[3][i]==wrong && f.a[1][i]!=wrong && f.a[2][i]!=wrong)
f.a[3][i]=f.a[2][i]*2-f.a[1][i];
}
}
return 1;
}
void dfs(node f,int k)
{
int i,j,l;
if (k==10)
{
vis=1;
r=f;
return;
}
i=k/3+1;
j=(k-1)%3+1;
if (f.a[i][j]==wrong)
{
node ff;
for (l=0;l<4;l++)
{
ff=f;
ff.a[i][j]=l; ///maybe can define by odd/even in matrix
if (!vis && add(ff) && check(ff))
dfs(ff,k+1);
}
}
else
{
if (!vis)
dfs(f,k+1);
}
}
int main()
{
int q,i,j;
scanf("%d",&q);
while (q--)
{
for (i=1;i<=3;i++)
for (j=1;j<=3;j++)
{
scanf("%s",str);
if (strcmp(str,"?")==0)
f.a[i][j]=wrong;
else
f.a[i][j]=atoi(str);
assert(abs(f.a[i][j])<=1e7 || f.a[i][j]==wrong);
}
add(f);
vis=0;
dfs(f,1);
print(r);
assert(vis==1);
assert(check(r));
assert(complete(r));
}
return 0;
}