*程序的思想就是广度搜索,有一个技巧是把二维数组一维化,这样速度会快一些*/
#include <stdio.h>FILE *fp;
long count=1;
int [362880];/*记录这个状态是否出现过*/
int id,matrixl[2]={1,0};
int matrix[2][262880][10]={2,3,4,5,6,7,8,9,1,8};/*初始状态,1表示0,2表示1……,最后的8是指空格在数组的第8个位置*/
const int swpl[9]={2,3,2,3,4,3,2,3,2};/*空格在第N个位置时可以和几个位置的数交换*/
const int fact[9]={40320,5040,720,120,24,6,2,1,1};/*1-8的阶乘*/
const int swap[9][4]={{1,3},{0,2,4},{1,5},
{0,4,6},{1,3,5,7},{2,4,8},
{3,7},{4,6,8},{5,7}};/*空格在第N个位置,可以与它交换的是哪些位置*/long pos(int a[]){/*算这个状态(排列)对应数组中的第n个元素*/
int i,j,k;
long n=0;
for (i=0;i<9;i++){
for (j=0,k=1;j<i;j++)
if (a[j]<a[i]) k++;
n+=(a[i]-k)*fact[i];
}
return n;
}void print(int matrix[]){
fprintf(fp,"%d %d %d\n",matrix[0]-1,matrix[1]-1,matrix[2]-1);
fprintf(fp,"%d %d %d\n",matrix[3]-1,matrix[4]-1,matrix[5]-1);
fprintf(fp,"%d %d %d\n\n",matrix[6]-1,matrix[7]-1,matrix[8]-1);
}void search(){
int i,j,k,l,temp,id2,zero;
long p;
while (matrixl[id]){
id2=(id+1)%2;
for (j=0,l=0;j<matrixl[id];++j){
zero=matrix[id][j][9];
for (i=0;i<swpl[zero];++i){
temp=matrix[id][j][zero];
matrix[id][j][zero]=matrix[id][j][swap[zero][i]];
matrix[id][j][swap[zero][i]]=temp;
p=pos(matrix[id][j]);
if (![p]){
count++;
[p]=1;
print (matrix[id][j]);
for (k=0;k<9;k++)
matrix[id2][l][k]=matrix[id][j][k];
matrix[id2][l++][9]=swap[zero][i];
}
temp=matrix[id][j][zero];
matrix[id][j][zero]=matrix[id][j][swap[zero][i]];
matrix[id][j][swap[zero][i]]=temp;
}
}
id=(id+1)%2;
matrixl[id]=l;
}
}void main(){
if ((fp=fopen("d:\\8.txt","w"))==NULL)
return;
[pos(matrix[0][0])]=1;
print (matrix[0][0]);
search();
fprintf(fp,"%ld\n",count);
printf("%ld\n",count);
fclose (fp);
}
#include <stdio.h>FILE *fp;
long count=1;
int [362880];/*记录这个状态是否出现过*/
int id,matrixl[2]={1,0};
int matrix[2][262880][10]={2,3,4,5,6,7,8,9,1,8};/*初始状态,1表示0,2表示1……,最后的8是指空格在数组的第8个位置*/
const int swpl[9]={2,3,2,3,4,3,2,3,2};/*空格在第N个位置时可以和几个位置的数交换*/
const int fact[9]={40320,5040,720,120,24,6,2,1,1};/*1-8的阶乘*/
const int swap[9][4]={{1,3},{0,2,4},{1,5},
{0,4,6},{1,3,5,7},{2,4,8},
{3,7},{4,6,8},{5,7}};/*空格在第N个位置,可以与它交换的是哪些位置*/long pos(int a[]){/*算这个状态(排列)对应数组中的第n个元素*/
int i,j,k;
long n=0;
for (i=0;i<9;i++){
for (j=0,k=1;j<i;j++)
if (a[j]<a[i]) k++;
n+=(a[i]-k)*fact[i];
}
return n;
}void print(int matrix[]){
fprintf(fp,"%d %d %d\n",matrix[0]-1,matrix[1]-1,matrix[2]-1);
fprintf(fp,"%d %d %d\n",matrix[3]-1,matrix[4]-1,matrix[5]-1);
fprintf(fp,"%d %d %d\n\n",matrix[6]-1,matrix[7]-1,matrix[8]-1);
}void search(){
int i,j,k,l,temp,id2,zero;
long p;
while (matrixl[id]){
id2=(id+1)%2;
for (j=0,l=0;j<matrixl[id];++j){
zero=matrix[id][j][9];
for (i=0;i<swpl[zero];++i){
temp=matrix[id][j][zero];
matrix[id][j][zero]=matrix[id][j][swap[zero][i]];
matrix[id][j][swap[zero][i]]=temp;
p=pos(matrix[id][j]);
if (![p]){
count++;
[p]=1;
print (matrix[id][j]);
for (k=0;k<9;k++)
matrix[id2][l][k]=matrix[id][j][k];
matrix[id2][l++][9]=swap[zero][i];
}
temp=matrix[id][j][zero];
matrix[id][j][zero]=matrix[id][j][swap[zero][i]];
matrix[id][j][swap[zero][i]]=temp;
}
}
id=(id+1)%2;
matrixl[id]=l;
}
}void main(){
if ((fp=fopen("d:\\8.txt","w"))==NULL)
return;
[pos(matrix[0][0])]=1;
print (matrix[0][0]);
search();
fprintf(fp,"%ld\n",count);
printf("%ld\n",count);
fclose (fp);
}
解决方案 »
免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货