RT,我搜出了字典序更小的解
如测试点6,case 7:
输入:
1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1
测试数据的输出:
1 2 13
20 19 14
21 18 15
26 3 12
25 4 5
22 17 16
27 10 11
24 9 6
23 8 7
更优的解:
1 2 23
4 3 24
5 6 27
10 19 22
9 18 25
8 7 26
11 20 21
12 17 16
13 14 15
我是按照前者做的,但是头两个点超时....,另外由于对字典序的理解不一样,只有10分。
下面是我的代码,请高手赐教:
1.如何不超时。
2.如何保证按照输出序列比较,第一个搜出的解字典序最小
#include <stdio.h>
int s[26];
int v[3][3][3];
int d[27][3];
int dic[27];
int dc[6][3]={
-1,0,0,
0,-1,0,
0,0,-1,
0,0,1,
0,1,0,
1,0,0
};
int dfs(int deep)
{
int j,ret=0;
if(deep==27)return 1;
if(s[deep-1])
{
for(j=0;j<6;j++)
{
if(dic[deep-1]!=j)
{
d[deep][0]=d[deep-1][0]+dc[j][0];
d[deep][1]=d[deep-1][1]+dc[j][1];
d[deep][2]=d[deep-1][2]+dc[j][2];
if( (d[deep][0]>-1)&&(d[deep][0]<3)&&(d[deep][1]>-1)&&(d[deep][1]<3)&&(d[deep][2]>-1)&&(d[deep][2]<3)&&(v[d[deep][0]][d[deep][1]][d[deep][2]]==-1))
{
dic[deep]=j;
v[d[deep][0]][d[deep][1]][d[deep][2]]=deep;
ret=dfs(deep+1);
if(ret) return ret;
v[d[deep][0]][d[deep][1]][d[deep][2]]=-1;
}
}
}
}
else
{
d[deep][0]=d[deep-1][0]+dc[dic[deep-1]][0];
d[deep][1]=d[deep-1][1]+dc[dic[deep-1]][1];
d[deep][2]=d[deep-1][2]+dc[dic[deep-1]][2];
if( (d[deep][0]>-1)&&(d[deep][0]<3)&&(d[deep][1]>-1)&&(d[deep][1]<3)&&(d[deep][2]>-1)&&(d[deep][2]<3)&&(v[d[deep][0]][d[deep][1]][d[deep][2]]==-1))
{
dic[deep]=dic[deep-1];
v[d[deep][0]][d[deep][1]][d[deep][2]]=deep;
ret=dfs(deep+1);
if(ret) return ret;
v[d[deep][0]][d[deep][1]][d[deep][2]]=-1;
}
}
return 0;
}
int solve()
{
int ret,i,j,k,t;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
{
d[0][0]=i; d[0][1]=j; d[0][2]=k;
v[d[0][0]][d[0][1]][d[0][2]]=0;
for(t=0;t<6;t++)
{
dic[0]=t;
ret=dfs(1);
if(ret) return ret;
}
v[d[0][0]][d[0][1]][d[0][2]]=-1;
}
return 0;
}
int main()
{
int i,j,k,n,a,b,c;
scanf("%d",&n);
for(i=0;i<n;i++)
{
memset(v,-1,sizeof(v));
for(j=1;j<=25;j++)
scanf("%d",&s[j]);
printf("Case %d:\n",i+1);
if(solve())
{
for(a=0;a<3;a++)
{
for(b=0;b<3;b++)
{
for(c=0;c<3;c++)
printf("%d ",v[a][b][c]+1);
printf("\n");
}
printf("\n");
}
printf("\n");
}
else
printf("No solution\n\n");
}
}