记得用记事本写一个输入和输出的状态放在工程里，名字为data.txt，一定要合规矩，否则这个程序非吃光你内存不可（我故意把深度控制给去掉了，虽有有节点深度的数据），因为我用的是广度优先搜索。当时感冒了，没认真组织，所以数据结构相当乱，指针漫天飞，光是检查指针越界访问的问题都花了我很长时间。 示例输入： 2 0 8 1 6 3 7 5 41 2 3 8 0 4 7 6 5 // OctNumQue.cpp : 定义控制台应用程序的入口点。// #include "stdafx.h"int EndState[3][3];int EPMove[4][2];UnCertainTree *Node;UnCertainTree *Solution;bool SateEqualCheck(UnCertainTree *Dest);/////////检测void EvaluateData(UnCertainTree *Dest,UnCertainTree *SouData);bool EmpPosMove(UnCertainTree *Dest,UnCertainTree *SouData,int Direction);void SpreadTree(BrothersList *BList);int _tmain(int argc, _TCHAR* argv[]){ ifstream DataFile; BrothersList *BList; ///////////////////////////////初始化根节点 Node=(UnCertainTree*)malloc(sizeof(UnCertainTree)); BList=(UnCertainTree*)malloc(sizeof(UnCertainTree)); Node->Brother=NULL; Node->Parent=NULL; for (int i=0;i<3;i++)  Node->Child[i]=NULL; DataFile.open("data.txt"); if (DataFile.fail()) {  cout<<"Can't find the data file."<<endl;  return 0; } for (int i=0;i<3;i++)     for (int j=0;j<3;j++)  {      DataFile>>Node->Poinfor[i][j];   if (Node->Poinfor[i][j]==EmpPos)   {    Node->EmpPosX=i;    Node->EmpPosY=j;   }  } for (int i=0;i<3;i++)  for (int j=0;j<3;j++)   DataFile>>EndState[i][j]; Node->Depth=0; BList->Brother=Node; DataFile.close(); ///////////////////////////////////////// EPMove[0][0]=1; EPMove[0][1]=0; EPMove[1][0]=0; EPMove[1][1]=-1; EPMove[2][0]=-1; EPMove[2][1]=0; EPMove[3][0]=0; EPMove[3][1]=1; SpreadTree(BList); cout<<Solution->Depth<<endl; while(Solution!=NULL) {  for (int i=0;i<3;i++)  {   for (int j=0;j<3;j++)    cout<<Solution->Poinfor[i][j]<<' ';   cout<<endl;  }  cout<<endl;  Solution=Solution->Parent; } return 0;} /////////////////////////////状态检测bool SateEqualCheck(UnCertainTree *Dest){ for (int i=0;i<3;i++)  for (int j=0;j<3;j++)  {   if (Dest->Poinfor[i][j]!=EndState[i][j])    return FALSE;  } return TRUE;}/////////////////////数组赋值void EvaluateData(UnCertainTree *Dest,UnCertainTree *SouData){ for (int i=0;i<3;i++)  for (int j=0;j<3;j++)   Dest->Poinfor[i][j]=SouData->Poinfor[i][j];} ////////////////////////////生成状态空间树void SpreadTree(BrothersList *BList){ BrothersList *BListTmp,*BListNew,*NewTmp; int SpinNum; ChildTree *SpreadTmp; BListNew=(BrothersList*)malloc(sizeof(UnCertainTree)); NewTmp=BListNew; BListTmp=BList; while(BListTmp->Brother!=NULL) {  BListTmp=BListTmp->Brother;  SpinNum=0;        for (int i=0;i<4;i++)        {   if (BListTmp->EmpPosX+EPMove[i][0]>2||BListTmp->EmpPosX+EPMove[i][0]<0)    continue;   if (BListTmp->EmpPosY+EPMove[i][1]>2||BListTmp->EmpPosY+EPMove[i][1]<0)    continue;   if (BListTmp->Parent!=NULL&&BListTmp->EmpPosX+EPMove[i][0]==BListTmp->Parent->EmpPosX&&     BListTmp->EmpPosY+EPMove[i][1]==BListTmp->Parent->EmpPosY)    continue;            SpreadTmp=(ChildTree*)malloc(sizeof(UnCertainTree));   BListTmp->Child[SpinNum++]=SpreadTmp;   if(EmpPosMove(SpreadTmp,BListTmp,i))   {    Solution=SpreadTmp;    return;   }   NewTmp->Brother=SpreadTmp;     //////兄弟链表   NewTmp=SpreadTmp;        } }    if(BListNew->Brother->Depth<20)    SpreadTree(BListNew);/////递归调用}////////空格移动bool EmpPosMove(UnCertainTree *Dest,UnCertainTree *SouData,int Direction){    Dest->Brother=NULL; Dest->Parent=SouData; EvaluateData(Dest,SouData); Dest->EmpPosX=SouData->EmpPosX+EPMove[Direction][0]; Dest->EmpPosY=SouData->EmpPosY+EPMove[Direction][1]; Dest->Poinfor[SouData->EmpPosX][SouData->EmpPosY]=  Dest->Poinfor[Dest->EmpPosX][Dest->EmpPosY]; Dest->Poinfor[Dest->EmpPosX][Dest->EmpPosY]=EmpPos; Dest->Depth=SouData->Depth+1; if(SateEqualCheck(Dest))  return TRUE; for(int i=0;i<3;i++)  Dest->Child[i]=NULL; return false;} 以上就是主程序 // stdafx.h : 标准系统包含文件的包含文件，// 或是经常使用但不常更改的// 特定于项目的包含文件// #pragma once#include "targetver.h"#include <iostream>#include <fstream>#include <istream>#include <stdio.h>#include <tchar.h>#include <Windows.h>using namespace std;typedef struct UnCertainTree{ int Poinfor[3][3]; int Depth; int EmpPosX,EmpPosY; UnCertainTree * Parent; UnCertainTree * Brother; UnCertainTree * Child[3];}BrothersList,ChildTree; // TODO: 在此处引用程序需要的其他头文件包含文件 #pragma once // 以下宏定义要求的最低平台。要求的最低平台// 是具有运行应用程序所需功能的 Windows、Internet Explorer 等产品的// 最早版本。通过在指定版本及更低版本的平台上启用所有可用的功能，宏可以// 正常工作。 // 如果必须要针对低于以下指定版本的平台，请修改下列定义。// 有关不同平台对应值的最新信息，请参考 MSDN。#ifndef _WIN32_WINNT            // 指定要求的最低平台是 Windows Vista。#define _WIN32_WINNT 0x0600     // 将此值更改为相应的值，以适用于 Windows 的其他版本。#endif#define EmpPos 0 可有可无的宏定义。 后面一篇就是这个程序的算法，实在是懒得去写注释，中英文切换很烦人。

评论