L
liangzhusen
Unregistered / Unconfirmed
GUEST, unregistred user!
#include <stdio.h>
#include <memory.h>
#define E_SIZE 3
#define N (E_SIZE*E_SIZE)
#define TOTAL_STATE 362880 //N!
int order2number(char order[N]){
int number=0,i,j;
for(i=0;i<N-1;i++){
int t=order;
for(j=0;j<i;j++)
if(order[j]<order)t--;
number*=(N-i);
number+=t;
}
return number;
}
void number2order(int number,char order[N]){
int i,j;
int used[N];
memset(used,0,sizeof(used));
order[N-1]=0;
for(i=N-2;i>=0;i--)
{
order=number%(N-i);
number/=N-i;
}
used[order[0]]=1;
for(i=1;i<N;i++){
for(j=0;;j++){
if(used[j])order++;
if(j==order){
used[j]=1;
break;
}
}
}
}
int GetRight(const char order[N]){//move data right and empty left
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i%E_SIZE==0){
return -1;
}else
{
norder=norder[i-1];
norder[i-1]=0;
return order2number(norder);
}
}
int GetLeft(const char order[N]){
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i%E_SIZE==E_SIZE-1){
return -1;
}else
{
norder=norder[i+1];
norder[i+1]=0;
return order2number(norder);
}
}
int GetDown(const char order[N]){
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i<E_SIZE){
return -1;
}else
{
norder=norder[i-E_SIZE];
norder[i-E_SIZE]=0;
return order2number(norder);
}
}
int GetUp(const char order[N]){
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i>=E_SIZE*(E_SIZE-1)){
return -1;
}else
{
norder=norder[i+E_SIZE];
norder[i+E_SIZE]=0;
return order2number(norder);
}
}
typedef int (*MoveFun)(const char order[N]);
MoveFun funs[4]={GetLeft,GetRight,GetUp,GetDown};
int quicktest(const char nInput[N],const char nOutput[N])
{
char input[N];
int i,o,ix,iy,ox,oy;
memcpy(input,nInput,sizeof(input));
for(o=0;o<N;o++)if(nOutput[o]==0)break;
for(i=0;i<N;i++)if(input==0)break;
ox=o%E_SIZE;
oy=o/E_SIZE;
ix=i%E_SIZE;
iy=i/E_SIZE;
//making empty in same place.
while(ix<ox){//moving empty right
input[ix+iy*E_SIZE]=input[ix+1+iy*E_SIZE];
input[ix+1+iy*E_SIZE]=0;
ix++;
}
while(iy<oy){//moving empty do
wn
input[ix+iy*E_SIZE]=input[ix+(iy+1)*E_SIZE];
input[ix+(iy+1)*E_SIZE]=0;
iy++;
}
while(ix>ox){
input[ix+iy*E_SIZE]=input[ix-1+iy*E_SIZE];
input[ix-1+iy*E_SIZE]=0;
ix--;
}
while(iy>oy){
input[ix+iy*E_SIZE]=input[ix+(iy-1)*E_SIZE];
input[ix+(iy-1)*E_SIZE]=0;
iy--;
}
o=0;
for(i=0;i<N;i++){
if(nOutput!=input){
int j;
for(j=i+1;j<N;j++)
if(input[j]==nOutput)
break;
input[j]=input;
input=nOutput;
o++;//o record count of swap.
}
}
return (o&1)==0;//return true while o is even number.
}
int ValidInput(const char input[N]){
char nMask[N];int i;
memset(nMask,0,sizeof(nMask));
for(i=0;i<N;i++){
if(input<0¦¦input>=N¦¦nMask[input])
return 0;
nMask[input]=1;
}
return 1;
}
void OutputState(const char output[N])
{
int i,j;
for(i=0;i<E_SIZE;i++){
for(j=0;j<E_SIZE;j++){
printf("%d ",output[i*E_SIZE+j]);
}
printf("/n");
}
}
void InputState(char input[N]){
int i;
for(i=0;i<N;i++){
scanf("%d",input+i);
}
}
char bSearched[TOTAL_STATE];
short nDistance[TOTAL_STATE];
int nPrev[TOTAL_STATE];
int nQueue[TOTAL_STATE];
int nHead1;
int nTail1;
int nHead2;
int nTail2;
int nStart;
int nend;
void Input(){
char nInput[N];
char nOutput[N];
startstate:
printf("Please input Start state:/n");
InputState(nInput);
if(!ValidInput(nInput))
{
printf("Invalid input/n");
goto startstate;
}
endstate:
printf("Please input End state:/n");
InputState(nOutput);
if(!ValidInput(nOutput))
{
printf("Invalid input/n");
goto endstate;
}
if(!quicktest(nInput,nOutput))
{
printf("Cannot move to the destining state/n");
printf("Suggestion: Swap two nonzero number/n");
goto endstate;
}
nStart=order2number(nInput);
nEnd=order2number(nOutput);
}
int IsQueue1Empty(){
return nHead1==nTail1;
}
int IsQueue2Empty(){
return nHead2==nTail2;
}
int SizeOfQueue1(){return nTail1-nHead1;}
int SizeOfQueue2(){return nHead2-nTail2;}
int GetQueue1(){
return nQueue[nHead1++];
}
int GetQueue2(){
return nQueue[nHead2--];
}
int PutQueue1(int i){//return true if have been put in Q2.
if(bSearched==1)//have been put in Q1
return 0;
if(bSearched==2)//have been put in Q2
return 1;
nQueue[nTail1++]=i;
bSearched=1;
return 2;
}
int PutQueue2(int i){
if(bSearched==2)
return 0;
if(bSearched==1)
return 1;
nQueue[nTail2--]=i;
bSearched=2;
return 2;
}
void EndInQ1(int cur,int prev)
{
int nSave;
char state[N];
int nShortest=nDistance[cur]+nDistance[prev]+1;
nSave=cur;
while(nPrev[prev]!=-1){//Inverse the list.
int n;
n=nSave;
nSave=prev;
prev=nPrev[prev];
nPrev[nSave]=n;
}
nPrev[prev]=nSave;
nSave=prev;
printf("/n");
while(nSave!=-1){
number2order(nSave,state);
OutputState(state);
printf("/n");
nSave=nPrev[nSave];
}
printf("Shortest moving cost %d/n",nShortest);
}
void EndInQ2(int cur,int prev)
{
int nSave;
char state[N];
int nShortest=nDistance[cur]+nDistance[prev]+1;
nSave=prev;
while(nPrev[cur]!=-1){
int n;
n=nSave;
nSave=cur;
cur=nPrev[cur];
nPrev[nSave]=n;
}
nPrev[cur]=nSave;
nSave=cur;
printf("/n");
while(nSave!=-1){
number2order(nSave,state);
OutputState(state);
printf("/n");
nSave=nPrev[nSave];
}
printf("Shortest moving cost %d/n",nShortest);
}
int main(){
Input();
nHead2=nTail2=TOTAL_STATE-1;
if(nStart==nEnd){
printf("Input is same as output/n");
return 0;
}
memset(nDistance,-1,sizeof(nDistance));
memset(nPrev,-1,sizeof(nPrev));
nDistance[nStart]=nDistance[nEnd]=0;
PutQueue1(nStart);
PutQueue2(nEnd);
while(1){//while(!IsQueue1Empty()&&!IsQueue2Empty()){//we could use while(1) because we can always get a result
int size,i;
size=SizeOfQueue1();
for(i=0;i<size;i++){
int q=GetQueue1();
char state[N];
int j;
number2order(q,state);
for(j=0;j<4;j++){
int x;
x=funs[j](state);
if(x!=-1){
switch(PutQueue1(x)){
case 2://new put.
nDistance[x]=nDistance[q]+1;
nPrev[x]=q;
break;
case 1://finished
EndInQ1(x,q);
return 0;
}
}
}
}
size=SizeOfQueue2();
for(i=0;i<size;i++){
int q=GetQueue2();
char state[N];
int j;
number2order(q,state);
for(j=0;j<4;j++){
int x;
x=funs[j](state);
if(x!=-1){
switch(PutQueue2(x)){
case 2://new put
nDistance[x]=nDistance[q]+1;
nPrev[x]=q;
break;
case 1://finished
EndInQ2(x,q);
return 0;
这程序编译时说#define TOTAL_STATE 362880 //N!这数太大了,什么原因,怎改,程序别人是是
编好了的,应该没问题[blue][/blue]
#include <memory.h>
#define E_SIZE 3
#define N (E_SIZE*E_SIZE)
#define TOTAL_STATE 362880 //N!
int order2number(char order[N]){
int number=0,i,j;
for(i=0;i<N-1;i++){
int t=order;
for(j=0;j<i;j++)
if(order[j]<order)t--;
number*=(N-i);
number+=t;
}
return number;
}
void number2order(int number,char order[N]){
int i,j;
int used[N];
memset(used,0,sizeof(used));
order[N-1]=0;
for(i=N-2;i>=0;i--)
{
order=number%(N-i);
number/=N-i;
}
used[order[0]]=1;
for(i=1;i<N;i++){
for(j=0;;j++){
if(used[j])order++;
if(j==order){
used[j]=1;
break;
}
}
}
}
int GetRight(const char order[N]){//move data right and empty left
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i%E_SIZE==0){
return -1;
}else
{
norder=norder[i-1];
norder[i-1]=0;
return order2number(norder);
}
}
int GetLeft(const char order[N]){
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i%E_SIZE==E_SIZE-1){
return -1;
}else
{
norder=norder[i+1];
norder[i+1]=0;
return order2number(norder);
}
}
int GetDown(const char order[N]){
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i<E_SIZE){
return -1;
}else
{
norder=norder[i-E_SIZE];
norder[i-E_SIZE]=0;
return order2number(norder);
}
}
int GetUp(const char order[N]){
char norder[N];
int i;
memcpy(norder,order,N*sizeof(char));
for(i=0;i<N;i++)if(order==0)break;//find empty position;
if(i>=E_SIZE*(E_SIZE-1)){
return -1;
}else
{
norder=norder[i+E_SIZE];
norder[i+E_SIZE]=0;
return order2number(norder);
}
}
typedef int (*MoveFun)(const char order[N]);
MoveFun funs[4]={GetLeft,GetRight,GetUp,GetDown};
int quicktest(const char nInput[N],const char nOutput[N])
{
char input[N];
int i,o,ix,iy,ox,oy;
memcpy(input,nInput,sizeof(input));
for(o=0;o<N;o++)if(nOutput[o]==0)break;
for(i=0;i<N;i++)if(input==0)break;
ox=o%E_SIZE;
oy=o/E_SIZE;
ix=i%E_SIZE;
iy=i/E_SIZE;
//making empty in same place.
while(ix<ox){//moving empty right
input[ix+iy*E_SIZE]=input[ix+1+iy*E_SIZE];
input[ix+1+iy*E_SIZE]=0;
ix++;
}
while(iy<oy){//moving empty do
wn
input[ix+iy*E_SIZE]=input[ix+(iy+1)*E_SIZE];
input[ix+(iy+1)*E_SIZE]=0;
iy++;
}
while(ix>ox){
input[ix+iy*E_SIZE]=input[ix-1+iy*E_SIZE];
input[ix-1+iy*E_SIZE]=0;
ix--;
}
while(iy>oy){
input[ix+iy*E_SIZE]=input[ix+(iy-1)*E_SIZE];
input[ix+(iy-1)*E_SIZE]=0;
iy--;
}
o=0;
for(i=0;i<N;i++){
if(nOutput!=input){
int j;
for(j=i+1;j<N;j++)
if(input[j]==nOutput)
break;
input[j]=input;
input=nOutput;
o++;//o record count of swap.
}
}
return (o&1)==0;//return true while o is even number.
}
int ValidInput(const char input[N]){
char nMask[N];int i;
memset(nMask,0,sizeof(nMask));
for(i=0;i<N;i++){
if(input<0¦¦input>=N¦¦nMask[input])
return 0;
nMask[input]=1;
}
return 1;
}
void OutputState(const char output[N])
{
int i,j;
for(i=0;i<E_SIZE;i++){
for(j=0;j<E_SIZE;j++){
printf("%d ",output[i*E_SIZE+j]);
}
printf("/n");
}
}
void InputState(char input[N]){
int i;
for(i=0;i<N;i++){
scanf("%d",input+i);
}
}
char bSearched[TOTAL_STATE];
short nDistance[TOTAL_STATE];
int nPrev[TOTAL_STATE];
int nQueue[TOTAL_STATE];
int nHead1;
int nTail1;
int nHead2;
int nTail2;
int nStart;
int nend;
void Input(){
char nInput[N];
char nOutput[N];
startstate:
printf("Please input Start state:/n");
InputState(nInput);
if(!ValidInput(nInput))
{
printf("Invalid input/n");
goto startstate;
}
endstate:
printf("Please input End state:/n");
InputState(nOutput);
if(!ValidInput(nOutput))
{
printf("Invalid input/n");
goto endstate;
}
if(!quicktest(nInput,nOutput))
{
printf("Cannot move to the destining state/n");
printf("Suggestion: Swap two nonzero number/n");
goto endstate;
}
nStart=order2number(nInput);
nEnd=order2number(nOutput);
}
int IsQueue1Empty(){
return nHead1==nTail1;
}
int IsQueue2Empty(){
return nHead2==nTail2;
}
int SizeOfQueue1(){return nTail1-nHead1;}
int SizeOfQueue2(){return nHead2-nTail2;}
int GetQueue1(){
return nQueue[nHead1++];
}
int GetQueue2(){
return nQueue[nHead2--];
}
int PutQueue1(int i){//return true if have been put in Q2.
if(bSearched==1)//have been put in Q1
return 0;
if(bSearched==2)//have been put in Q2
return 1;
nQueue[nTail1++]=i;
bSearched=1;
return 2;
}
int PutQueue2(int i){
if(bSearched==2)
return 0;
if(bSearched==1)
return 1;
nQueue[nTail2--]=i;
bSearched=2;
return 2;
}
void EndInQ1(int cur,int prev)
{
int nSave;
char state[N];
int nShortest=nDistance[cur]+nDistance[prev]+1;
nSave=cur;
while(nPrev[prev]!=-1){//Inverse the list.
int n;
n=nSave;
nSave=prev;
prev=nPrev[prev];
nPrev[nSave]=n;
}
nPrev[prev]=nSave;
nSave=prev;
printf("/n");
while(nSave!=-1){
number2order(nSave,state);
OutputState(state);
printf("/n");
nSave=nPrev[nSave];
}
printf("Shortest moving cost %d/n",nShortest);
}
void EndInQ2(int cur,int prev)
{
int nSave;
char state[N];
int nShortest=nDistance[cur]+nDistance[prev]+1;
nSave=prev;
while(nPrev[cur]!=-1){
int n;
n=nSave;
nSave=cur;
cur=nPrev[cur];
nPrev[nSave]=n;
}
nPrev[cur]=nSave;
nSave=cur;
printf("/n");
while(nSave!=-1){
number2order(nSave,state);
OutputState(state);
printf("/n");
nSave=nPrev[nSave];
}
printf("Shortest moving cost %d/n",nShortest);
}
int main(){
Input();
nHead2=nTail2=TOTAL_STATE-1;
if(nStart==nEnd){
printf("Input is same as output/n");
return 0;
}
memset(nDistance,-1,sizeof(nDistance));
memset(nPrev,-1,sizeof(nPrev));
nDistance[nStart]=nDistance[nEnd]=0;
PutQueue1(nStart);
PutQueue2(nEnd);
while(1){//while(!IsQueue1Empty()&&!IsQueue2Empty()){//we could use while(1) because we can always get a result
int size,i;
size=SizeOfQueue1();
for(i=0;i<size;i++){
int q=GetQueue1();
char state[N];
int j;
number2order(q,state);
for(j=0;j<4;j++){
int x;
x=funs[j](state);
if(x!=-1){
switch(PutQueue1(x)){
case 2://new put.
nDistance[x]=nDistance[q]+1;
nPrev[x]=q;
break;
case 1://finished
EndInQ1(x,q);
return 0;
}
}
}
}
size=SizeOfQueue2();
for(i=0;i<size;i++){
int q=GetQueue2();
char state[N];
int j;
number2order(q,state);
for(j=0;j<4;j++){
int x;
x=funs[j](state);
if(x!=-1){
switch(PutQueue2(x)){
case 2://new put
nDistance[x]=nDistance[q]+1;
nPrev[x]=q;
break;
case 1://finished
EndInQ2(x,q);
return 0;
这程序编译时说#define TOTAL_STATE 362880 //N!这数太大了,什么原因,怎改,程序别人是是
编好了的,应该没问题[blue][/blue]