/* 现有3×3的九个方格，空出中心的方格，将数字1-8随机的放入到其它的8个方格中，
数字1不动，其它的数字可以移动，
   最终，使所有数字按1-8的顺序顺时针排列外围方格中。移动的规则是：
   都可以移向横排或竖排相临空着的方格，而且，都可以移向中心空着的方格。
   要求计算出移动移动最少的次数。
    
    函数接口： int minMove(int a[]);
    其中 a[] 表示从左上角顺时针放入的8个数。
*/
/*2006-2-25*/ 
/*算法介绍： 1。设定位置标号：从左上角按顺时针依次设定位置标号为1-8，中间的空格位置标号为0。
*2。创建一个类，其对象为数字1-8。为每个对象的属性包括位置标号pos和数字大小num。
*3。定义一个对象数组，数组元素依次为数字1-8。为方便起见，这里使每个元素的大小等于其下标值。
*4。从数字2开始依次按照移动规则操作每个数字，使其按顺序顺时针排列到外围方格中。
    操作方法：若数字n（2 <= n <=8 )已经位于n-1之后，则对n不做任何操作，直接操作n+1；
    若数字n不在n-1之后，则：
    1。若n处于中间的方格中（指位置标号为2，4，6，8处，非中间空格处），则将其移至
中间空格处，然后将其位置前面的数字依次按逆时针移动，直到空出一个合适的方格，即方格
的前一位置处是数字n-1，将n移到该空方格处。
    2。若n不处于中间的方格中（即位置标号为1，3，5，7处），则将其移到中间的方格中。
    具体操作为：将n位置前面的数字移至中间空格处，然后将它及其位置后面的数字依次按逆时针移动，
直到空出一个合适的方格，即方格的后一位置处的数字比n大或者是数字1，
将中间空格处的数字移到该空方格处。此时n已经处于中间的方格中。    
*5。累计每次移动，最后返回移动的次数，此即移动最少的次数。
*6。本程序还可以打印每次移动后各数字的分布情况（中间空格处无数字），
    用户可以将其打印出来以便帮助实际操作。 
*/ 
#include 
using namespace std;

int count = 0;   //全局变量，用来累计移动的次数 
const int Max = 8; //全局变量，表示数的个数 

class Date{   //创建一个类，用来描述每一个数字的大小和位置标号
    int pos;
    int num;
public:
    int GetPos()  //读取位置标号 
    {
        return pos;
    }
    int GetNum()//读取数字大小 
    {
        return num;
    }
    void SetPos(int p) //设置位置标号 
    {
        pos = p;
    }
    void SetNum(int n) //设置数字大小 
    {              
        num = n;
    }

    int PrePos() //读取该数字的前一位置标号 
    {
        if (pos == 1)
            return 8;
        else
            return pos-1;
    }
    
    Date operator =(Date A)
    {
        pos = A.GetPos();
        num = A.GetNum();
        
        return *this;
    }
};

void SetDate(const int a[], Date A[]);//根据传入的数据，设置对象数组 
void PrintDate(const Date A[]);//打印对象数组，即各数字的分布情况（中间空格处无数字）
void SortDate(Date A[]); //按照位置标号大小，用选择排序法对数组元素进行排序 
int NextPos(int pos); //传入一个位置标号，返回该位置之后的位置标号 
void MoveDate(Date A[], int blank, int n); //按要求移动数字 
bool IsMid(int pos);//传入一个位置标号，判断该位置是否处于中间 
void ToMid(Date A[], Date D); //将数字对象D移到外围方格中间的方格中
int ToCen(Date &D); //将数字对象D移到中间的空格格中
int Forward(Date &D);//传入一个数字对象，将其按逆时针顺序向前移动
int MinMove(int a[]); //计算出移动移动最少的次数

int main()             
{
    int a[Max] = {1, 2, 3, 4, 5, 6, 8, 7};

    cout << "c=" << MinMove(a) << "\n";  
      
    getchar();
    return 0;
}

int MinMove(int a[])
{
    Date A[Max+1];
    int blank;
    extern int count;
    
    SetDate(a, A); //根据传入的数据，设置对象数组 
    
    PrintDate(A); //打印对象数组，即各数字的分布情况（中间空格处无数字） 
  
    for (int i=2; i<=Max; i++) //从数字2开始依次按照移动规则操作每个数字
    {    
        if (A[i].PrePos() != A[i-1].GetPos()) //若数字i未按顺序排列 
        {        
            if (! IsMid(A[i].GetPos())) //若数字i不处于中间的方格中 
                ToMid(A, A[i]);  //则将其移到中间的方格中
                
        //    cout << "c=" << count << "\n";     
        //    PrintDate(A); 
        
            //若数字i已经按顺序排列了，跳过后面的操作，操作数字i+1 
            if (A[i].PrePos() == A[i-1].GetPos())
            {    
            //    cout << "c=" << count << "\n";
            //    PrintDate(A);   
                continue;
            }
            
            // 否则，把数字i移到中间空格处，并将其位置前面的数字依次按逆时针移动 
            //直到空出一个合适的方格，即方格的前一位置处是数字i-1，将i移到该空方格处。
            blank = ToCen(A[i]);
            MoveDate(A, blank, i); 
            
        //    cout << "c=" << count << "\n";  
        //    PrintDate(A); 
        }
    }
    
   // PrintDate(A);  
 
    return count;
}

/*函数介绍: 传入一个位置标号，返回该位置之后的位置标号 
*/
int NextPos(int pos)
{
    if (pos == 8)
        return 1;
    else
        return pos + 1;
}

/*函数介绍: 若n处于中间的方格中（指位置标号为2，4，6，8处，非中间空格处），则将其移至
中间空格处，然后将其位置前面的数字依次按逆时针移动，直到空出一个合适的方格，即方格
的前一位置处是数字n-1，将n移到该空方格处。 
*形参： Date A[]：对象数组 
    int blank：空格处的位置标号
    int n：正在处理的数字对象的下标，即其数字的大小 
*/
void MoveDate(Date A[], int blank, int n)
{
    extern int count;
    
    while (1)
    {
        for (int i=1; i<=Max; i++) //将n的位置前面的数字依次按逆时针移动
        {
            if (A[i].PrePos() == blank)
            {
                blank = Forward(A[i]);    
                count++;
                break;
            }
        }
        
        //如果空格在中间，并且空格之前的数字为n-1，则停止移动其他数字 
        if ((IsMid(blank)) && (blank == NextPos(A[n-1].GetPos())))
            break;
    }
    
    A[n].SetPos(blank);  //将n移到空方格处
    count++;        
}

/*函数介绍: 传入一个位置标号，判断该位置是否处于中间 
*/
bool IsMid(int pos)
{
    if (pos == 2 ||   pos == 4 || pos == 6 || pos == 8)
        return true;
    else
        return false;
}

/*函数介绍: 若n不处于中间的方格中（即位置标号为1，3，5，7处），则将其移到中间的方格中。
    具体操作为：将n位置前面的数字移至中间空格处，然后将它及其位置后面的数字依次按逆时针移动，
直到空出一个合适的方格，即方格的后一位置处的数字比n大或者是数字1，
将中间空格处的数字移到该空方格处。此时n已经处于中间的方格中。
*形参： Date A[]：对象数组 
    Date D：正在处理的数字对象 
*/
void ToMid(Date A[], Date D)
{
    extern int count;
    int flag = 0;     
    int blank;
    
    for (int i=1; i<=Max; i++)  //将n位置前面的数字移至中间空格处
    {
        if (A[i].GetPos() == D.PrePos())
        {     
            blank = ToCen(A[i]);
            break;
        }
    }    
       
    while (1)
    {    
        for (int i=1; i<=Max; i++) //将它及其位置后面的数字依次按逆时针移动
        {
            if (A[i].PrePos() == blank)
            {     
                blank = Forward(A[i]);
                count++;      
                break;
            }
        }
        
        if (IsMid(blank))//直到发现一个合适的空格 
        {   
            for (int i=1; i<=Max; i++)
            {
                if ((A[i].GetPos() == NextPos(blank)) && 
                ((A[i].GetNum() > D.GetNum()) || (A[i].GetNum() == 1)))
                {  
                    flag = 1;
                    break;
                }
            }
        }
        
        if (flag == 1)
            break;
    }
    
    for (int i=1; i<=Max; i++) // 将中间空格处的数字n移到该空方格处
    {
        if (A[i].GetPos() == 0)
        {   
            A[i].SetPos(blank);
            count++;   
            break;
        }
    }    
}

/*函数介绍: 传入一个数字对象，将其移到中间空格（位置标号为0）处 
*/
int ToCen(Date &D)
{
    extern int count;
    int blank = D.GetPos();
    
    D.SetPos(0);
    count++;    
    
    return blank;
}

/*函数介绍: 传入一个数字对象，将其按逆时针顺序向前移动
*/
int Forward(Date &D)
{
    int blank = D.GetPos();
    
    D.SetPos(D.PrePos());
    
    return blank;
}

/*函数介绍: 根据传入的数据，设置对象数组 
*/
void SetDate(const int a[], Date A[])
{
    for (int i=0; i    { 
        A[a[i]].SetPos(i+1);       
        A[a[i]].SetNum(a[i]);
    }    
}

/*函数介绍: 打印对象数组，即各数字的分布情况（中间空格处无数字） 
*/
void PrintDate(const Date A[])
{
    Date B[Max+1];
    
    for (int i=1; i<=Max; i++)
        B[i] = A[i];
    
    SortDate(B); //按照位置标号大小，对对象数组的元素进行排序 
    
    for (int i=1; i<=3; i++)
        cout << B[i].GetNum() << " ";
        
    cout << "\n";
    cout << B[8].GetNum() << "   "; 
    cout << B[4].GetNum() << "\n";
    
    for (int i=7; i>=5; i--)
        cout << B[i].GetNum() << " ";    
                                     
    cout << "\n\n";
}

/*函数介绍: 按照位置标号大小，用选择排序法对数组元素进行排序 
*/
void SortDate(Date A[])
{
    int i, j, temp;
    Date T;
    
    for (i=1; i    {
        temp = i;
        for (j=i+1; j<=Max; j++)
        {
            if (A[temp].GetPos() > A[j].GetPos())
                temp = j;
        }
        if (temp != i)
        {
            T = A[temp];
            A[temp] = A[i];
            A[i] = T;
        }
    }
}

评论