我的第一次……
第一次使用九維數組……
簡單地BFS即可。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
#define max_size 300000
const long change[ ][9]={{1,1,0,1,1,0,0,0,0},
{1,1,1,0,0,0,0,0,0},
{0,1,1,0,1,1,0,0,0},
{1,0,0,1,0,0,1,0,0},
{0,1,0,1,1,1,0,1,0},
{0,0,1,0,0,1,0,0,1},
{0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,1,1,0,1,1}};
struct
{
long count,front,rear,item[max_size][9];
}q;
void Clear()
{
q.count=0;q.front=0;q.rear=-1;
}
void Push(long *x)
{
q.count++;
q.rear++;
for(long i=0;i<9;i++)
q.item[q.rear][i]=x[i];
}
void Pop(long *x)
{
q.count--;
for(long i=0;i<9;i++)
x[i]=q.item[q.front][i];
q.front++;
}
bool Empty()
{
return (q.count==0);
}
int d[4][4][4][4][4][4][4][4][4];
int f[4][4][4][4][4][4][4][4][4];
long r[17];
void init()
{
for(long i=0;i<9;i++) scanf("%ld",&r[i]);
memset(d,-1,sizeof(d));
memset(f,-1,sizeof(f));
}
bool ok(long *x)
{
for(long i=0;i<9;i++)
if(x[i]) return false;
return true;
}
void bfs()
{
long t[17],s[17];
Clear();
d[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]][r[7]][r[8]]=0;
Push(r);
while(!Empty())
{
Pop(t);
if(ok(t)) break;
for(long i=0;i<9;i++)
{
for(long j=0;j<9;j++) s[j]=(t[j]+change[i][j])%4;
if(d[s[0]][s[1]][s[2]][s[3]][s[4]][s[5]][s[6]][s[7]][s[8]]==-1)
{
d[s[0]][s[1]][s[2]][s[3]][s[4]][s[5]][s[6]][s[7]][s[8]]=d[t[0]][t[1]][t[2]][t[3]][t[4]][t[5]][t[6]][t[7]][t[8]]+1;
f[s[0]][s[1]][s[2]][s[3]][s[4]][s[5]][s[6]][s[7]][s[8]]=i;
Push(s);
}
}
}
}
void output()
{
long t[17],ans[30],tot,tmp;
for(long i=0;i<9;i++) t[i]=0;
tot=0;
while(f[t[0]][t[1]][t[2]][t[3]][t[4]][t[5]][t[6]][t[7]][t[8]]!=-1)
{
tot++;
tmp=f[t[0]][t[1]][t[2]][t[3]][t[4]][t[5]][t[6]][t[7]][t[8]];
ans[tot]=tmp+1;
for(long i=0;i<9;i++)
if(change[tmp][i])
t[i]=(t[i]+3)%4;
}
bool first=true;
for(long i=tot;i>=1;i--)
{
if(first) first=false;
else printf(" ");
printf("%ld",ans[i]);
}
printf("\n");
}
int main()
{
init();
bfs();
output();
return 0;
}
posted on 2010-04-07 21:47
lee1r 閱讀(358)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索