蓝桥杯:历年试题PREV-42— 九宫幻方
今天训练的一道题。。明摆着的DFS在机房将近一个小时才写出来,还给写错了……(吐血),让大一大二同学见笑了。。233333333
#include<stdio.h>
#include<stdlib.h>
int sum;
int ans[4][4]={0},matrix[4][4]={0},book[10]={0};
int check(void)
{
int i,j;
for(i=1;i<=3;i++)
if(matrix[i][1]+matrix[i][2]+matrix[i][3]!=15)
return 0;
for(j=1;j<=3;j++)
if(matrix[1][j]+matrix[2][j]+matrix[3][j]!=15)
return 0;
if(matrix[1][1]+matrix[2][2]+matrix[3][3]!=15)
return 0;
if(matrix[1][3]+matrix[2][2]+matrix[3][1]!=15)
return 0;
return 1;
}
void DFS(int sp)
{
int i,j;
if(sp>9)
{
if(check())
{
sum++;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
ans[i][j]=matrix[i][j];
}
return;
}
int si=(sp+2)/3,sj=sp%3;
if(!sj) sj=3;
if(matrix[si][sj])
{
DFS(sp+1);
return;
}
for(i=1;i<=9;i++)
{
if(book[i])
continue;
book[i]=1;
matrix[si][sj]=i;
DFS(sp+1);
matrix[si][sj]=0;
book[i]=0;
}
return;
}
int main(int argc, char *argv[])
{
int i,j;
for(i=1;i<=3;i++)
{
for(j=1;j<=3;j++)
{
scanf("%d",&matrix[i][j]);
book[matrix[i][j]]=1;
}
}
matrix[2][2]=5;
sum=0;
DFS(1);
if(sum==1)
{
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
printf("%d%c",ans[i][j],j==3?'\n':' ');
}
else if(sum>1)
printf("Too Many\n");
return 0;
}