2020 Google Code Jam 资格赛 E
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,m,a[55][55],b[55];
int debug()
{
printf("-------------\n");
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
printf("%d ",a[j][k]);
printf("\n");
}
printf("--------------\n");
}
int main()
{
scanf("%d",&T);
for(int t=1;t<=T;t++)
{
memset(a,0,sizeof a);
scanf("%d%d",&n,&m);
printf("Case #%d: ",t);
if(m==n+1||m==n*n-1||(n==3&&m%3!=0))
{
printf("IMPOSSIBLE\n");
continue;
}
printf("POSSIBLE\n");
bool bo=false;
for(int i=1;i<=n;i++)
{
if(i*n==m)
{
bo=true;
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
{
a[j][k]=(j+n-k+(i-1))%n+1;
}
break;
}
}
if(bo)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
printf("%d ",a[j][k]);
printf("\n");
}
continue;
}
for(int i1=1;i1<=n&&m>2*i1&&!bo;i1++)
{
if((m-2*i1)%(n-2)==0&&(m-2*i1)/(n-2)<=n)
{
bo=true;
int i2=(m-2*i1)/(n-2);
for(int i=0;i<n-2;i++)
{
a[i][i]=i2;
}
a[n-1][n-2]=a[n-2][n-1]=i2;
a[n-1][n-1]=a[n-2][n-2]=i1;
for(int i=0;i<n-3;i++)
a[i][i+1]=i1;
a[n-3][0]=i1;
// debug();
int tb=0;
for(int i=1;i<=n;i++)
{
if(i!=i1&&i!=i2)
b[++tb]=i;
}
for(int i=0;i<n-2;i++)
{
tb=0;
for(int j=i+2;j<n;j++)
if(a[i][j]==0)
a[i][j]=b[++tb];
for(int j=0;j<i+2;j++)
if(a[i][j]==0)
a[i][j]=b[++tb];
}
a[n-2][0]=a[n-1][1]=b[1];
for(int i=2;i<n-2;i++)
a[n-2+(i%2==0?1:0)][i-2]=a[n-2+(i%2==0?0:1)][i]=b[i];
if(a[n-2][n-4]==0)
a[n-2][n-4]=a[n-1][n-3]=b[n-2];
else
a[n-2][n-3]=a[n-1][n-4]=b[n-2];
}
}
if(bo)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
printf("%d ",a[j][k]);
printf("\n");
}
continue;
}
for(int i1=1;i1<=n&&!bo;i1++)
for(int i2=i1+1;i1+i2<m&&i2<=n&&!bo;i2++)
{
if((m-i1-i2)%(n-2)==0&&(m-i1-i2)/(n-2)!=i1&&(m-i1-i2)/(n-2)!=i2&&(m-i1-i2)/(n-2)<=n)
{
int i3=(m-i1-i2)/(n-2);
// printf("%d %d %d\n",i1,i2,i3);
bo=true;
for(int i=0;i<n-2;i++)
a[i][i]=i3;
a[n-2][n-2]=i2;
a[n-1][n-1]=i1;
int tb=0;
for(int i=1;i<=n;i++)
{
if(i!=i1&&i!=i2&&i!=i3)
b[++tb]=i;
}
a[n-2][n-1]=a[n-1][n-2]=i3;
if(n&1)
{
for(int i=0;i<n-2;i++)
{
a[i+1][i]=a[i][i+1]=i&1?i2:i1;
}
a[n-1][0]=a[0][n-1]=i2;
// debug();
for(int i=0;i<n;i++)
{
tb=0;
for(int j=i;j<n;j++)
if(a[i][j]==0)
a[i][j]=b[++tb];
for(int j=0;j<i;j++)
if(a[i][j]==0)
a[i][j]=b[++tb];
}
}
else
{
for(int i=0;i<n-2;i+=2)
{
a[i+1][i]=i2;
a[i][i+1]=i1;
}
for(int i=0;i<n-2;i+=2)
{
a[i+2][i]=a[i+3][i+1]=b[1];
a[i+2][i+1]=i2;
a[i+3][i]=i1;
}
a[n-1][n-4]=a[n-2][n-3]=b[1];
a[n-2][n-4]=i1;
a[n-1][n-3]=i2;
a[0][n-2]=a[1][n-1]=b[1];
a[0][n-1]=i2;
a[1][n-2]=i1;
// debug();
for(int j=0;j<n;j+=2)
{
tb=2;
for(int i=j+4;i<n;i+=2)
{
a[i][j]=a[i+1][j+1]=b[tb];
a[i][j+1]=a[i+1][j]=b[tb+1];
tb+=2;
}
if(j!=n-2)
for(int i=0;i<j;i+=2)
{
a[i][j]=a[i+1][j+1]=b[tb];
a[i][j+1]=a[i+1][j]=b[tb+1];
tb+=2;
// debug();
}
else
for(int i=2;i<j;i+=2)
{
a[i][j]=a[i+1][j+1]=b[tb];
a[i][j+1]=a[i+1][j]=b[tb+1];
tb+=2;
}
}
}
}
}
if(bo)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<n;k++)
printf("%d ",a[j][k]);
printf("\n");
}
continue;
}
}
}
原文：https://www.cnblogs.com/DariusOrz/p/12661924.html