bashuma.cpp

C＋＋实现的八数码问题

#include <iostream>
#include <queue>
#include <set>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include "math.h"

using namespace std;

typedef struct state
{
   int s[3][3];
   int f,g,h;
   char move_from;
   public:
   state(int p[3][3])
   {
        for(int i=0;i<3;i++)
           for(int j=0;j<3;j++)
              this->s[i][j]=p[i][j];
   }
   state()
   {
   }
   void print_state()
   {
        for(int i=0;i<3;i++)
        {
        for(int j=0;j<3;j++)
            cout<<this->s[i][j]<<" ";
        cout<<endl;
        }
   }
   void calculate_h()
   {
        int m,n;
        this->h=0;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(s[i][j])
                {
                    m=s[i][j]/3;
                    n=s[i][j]%3-1;
                    this->h+=abs(i-m)+abs(j-n);
                }
                else
                {
                    this->h+=abs(i-2)+abs(j-2);
                }
            }
        }
   }
   state *pre;
}state;

typedef struct _tagcompare 
{
 bool operator() (const state &a, const state &b)
 {
   if(a.f>b.f)
   {
	   return true;
   }
   else
   {
	   if((a.f == b.f)&& (a.h > b.h))
	   {return true;}
	   else
	   {
		   if(a.f < b.f)
		   {return false;}
		   if((a.h==b.h)&&(a.g > b.g))
		   {return true;}
		   else
		   {return false;}
	   }
   }  
 }
}compare;

typedef struct _equal
{
	public:
	bool operator() (const state &a,const state &b)
	{
         for(int i=0;i<3;i++)
         {
             for(int j=0;j<3;j++)
             {
                if(a.s[i][j]!=b.s[i][j])
                return true;
             }
         }
		return false;
	}
}noequalto;

typedef priority_queue< state ,vector<state>,compare > pri_q;
pri_q state_q;

typedef set< state,noequalto > s_set;
s_set state_set;

void move(state &current,char m)
{
     for(int i=0;i<3;i++)
     {
         for(int j=0;j<3;j++)
         {
             if( current.s[i][j]==0 )
             {
                 switch(m)
                 {
                          case 'n':
                               current.s[i][j]=current.s[i-1][j];
                               current.s[i-1][j]=0;
                               break;
                          case 's':
                               current.s[i][j]=current.s[i+1][j];
                               current.s[i+1][j]=0;
                               break;
                          case 'w':
                               current.s[i][j]=current.s[i][j-1];
                               current.s[i][j-1]=0;
                               break;
                          case 'e':
                               current.s[i][j]=current.s[i][j+1];
                               current.s[i][j+1]=0;
                               break;
                 }
                 return;
             }     
         }
     }
     return;
}

bool can_move(int p[3][3],char m)
{
     switch(m)
     {
              case 'n':
                   if( p[0][0]!=0 && p[0][1]!=0 && p[0][2]!=0 )
                       return true;
                   else
                       return false;
                   break;
              case 's':
                   if( p[2][0]!=0 && p[2][1]!=0 && p[2][2]!=0 )
                       return true;
                   else
                       return false;
                   break;
              case 'w':
                   if( p[0][0]!=0 && p[1][0]!=0 && p[2][0]!=0 )
                       return true;
                   else
                       return false;
                   break;
              case 'e':
                   if( p[0][2]!=0 && p[1][2]!=0 && p[2][2]!=0 )
                       return true;
                   else
                       return false;
                   break;
              default:
                      break;
     }
}


vector<state> state_vector;

int search(state &);
bool isFinished(const state &);

void print_path()
{
     for(vector<state>::iterator it = state_vector.begin();it != state_vector.end();it++)
     {
         if(it->move_from != '0')
             cout<<it->move_from<<endl;
         it->print_state();
         //cout<<endl;
         
     }
}

int main()
{
    string pos,ss;
    ifstream in("bashuma.txt");
    int i=0,j=0;
    state current;
    while(getline(in,ss))
    {
        istringstream stream(ss);
        j=0;
        while(stream>>pos)
        {
            current.s[i][j]=atoi(pos.c_str());
            j++;
        }
        i++;
    }
    current.move_from='0';
    //current.print_state();
    if( isFinished(current) )
    {
        current.print_state();
    }
    else
    {
        search(current);
        print_path();
        state_set.clear();
    //state_q.clear();
        state_vector.clear();
    }
    cin>>ss;
    return 0;
}

bool not_exist(state &current)
{
   int quto;
   quto=state_set.size();
   state_set.insert(current);
   if( quto==state_set.size() )
       return false;
   else
       return true;
}

bool isFinished(const state &current)
{
     for(int i=0;i<3;i++)
         for(int j=0;j<3;j++)
             if( current.s[i][j] != 0 )
                 if( current.s[i][j] != i*3+j+1 )
                    return false;
                 else
                     continue;
             else
                 if( i!=2 || j!=2 )
                    return false;
                 else
                     continue;
     return true;
}

int search(state &current)
{
    state next;
    state_vector.push_back(current);
    for(int i=-1;i<=1;i++)
    {
        for(int j=-1;j<=1;j++)
        {
                if( i == -1 && j == 0 )
                {
                    if(can_move(current.s,'n'))
                    {
                        state temp(current.s);
                        move(temp,'n');
                        state set_temp(temp.s);
                        if( not_exist( set_temp ) )
                        {
                            temp.pre=&current;
                            temp.calculate_h();
                            temp.g=current.g+1;
                            temp.f=temp.g+temp.h;
                            temp.move_from='n';
                            if( isFinished(temp) )
                            {
                                state_vector.push_back(temp);
                                return 0;
                            }
                            else                                
                                state_q.push(temp);
                        }
                    }
                }
                else if( i == 0 && j ==-1 )
                {
                     if(can_move(current.s,'w'))
                     {
                        state temp(current.s);
                        move(temp,'w');
                        state set_temp(temp.s);
                        if( not_exist( set_temp ) )
                        {
                            temp.pre=&current;
                            temp.calculate_h();
                            temp.g=current.g+1;
                            temp.f=temp.g+temp.h;
                            temp.move_from='w';
                            if(isFinished(temp))
                            {
                                state_vector.push_back(temp);
                                return 0;
                            }
                            else
                                state_q.push(temp);
                        }
                     }
                }
                else if( i == 0 && j == 1 )
                {
                     if(can_move(current.s,'e'))
                     {
                        state temp(current.s);
                        move(temp,'e');
                        state set_temp(temp.s);
                        if( not_exist( set_temp ) )
                        {
                            temp.pre=&current;
                            temp.calculate_h();
                            temp.g=current.g+1;
                            temp.f=temp.g+temp.h;
                            temp.move_from='e';
                            if(isFinished(temp))
                            {
                                state_vector.push_back(temp);
                                return 0;
                            }
                            else
                                state_q.push(temp);
                        }
                     }
                }
                else if( i == 1 && j == 0 )
                {
                     if(can_move(current.s,'s'))
                     {
                        state temp(current.s);
                        move(temp,'s');
                        state set_temp(temp.s);
                        if( not_exist( set_temp ) )
                        {
                            temp.pre=&current;
                            temp.calculate_h();
                            temp.g=current.g+1;
                            temp.f=temp.g+temp.h;
                            temp.move_from='s';
                            if(isFinished(temp))
                            {
                                state_vector.push_back(temp);
                                return 0;
                            }
                            else
                                state_q.push(temp);
                        }
                     }
                }
        }
    }
    next=state_q.top();
    state_q.pop();
    search(next);
    return 0;
}