8nums.cpp

经典八数码问题,回溯法的解决

#include <fstream.h>

using namespace std;
ifstream fin("file.in");
ofstream fout("file.out");

class nums
{
//public:
        int style[3][3];
        int zerox,zeroy;
        int father,step;
        int inf;
public:
        void Getpoint(int obj[3][3])
       {
                int i,j;
                for(i=0;i<3,i++)
                {
                 for(j=0;j<3;j++)
                 {
                        if(obj[i][j]==0)
                        {
                               inf=step+(abs(i-zeroy)+abs(j-zerox));
                               break;
                        }
                 }
                }
       }
       void Move(int dx,int dy,int fa)
       {
                int temp;
                step++;
                father=fa;
                style[zeroy][zerox]=style[zeroy+dy][zerox+dx];
                style[zeroy+dy][zerox+dx]=0;

       }
       void Givevalue(int src[3][3])
       {
                int i,j;
                for(i=0;i<3;i++)
                {
                 for(j=0;j<3;j++)
                 {
                        style[i][j]=src[i][j];
                        if(!style[i][j]){zeroy=i;zerox=j;}
                 }
                }
       }
       void Init()
       {
                father=0;
                step=0;
                inf=0;
       }




nums work[10000];
int open=1,close=0;
const int movex[]={0,1,0,-1};
const int movey[]={1,0,-1,0};
void Init()
{
        int num[3][3];
       int i,j;
                for(i=0;i<3;i++)
                {
                 for(j=0;j<3;j++)
                 {
                        fin>>num[n][n];
                 }
                }
       work[0].Givevalue(num);
       work[0].Init();
}
void Expand()
{
        int i,j;
        for(i=0;i<4;i++)
        {
                work[open]=work[close];
                work[open].Move(movex[i],movey[i],close);
                
}
void main()
{
        Init;
        while(close<10000)
        {
                Expand()