text1.cpp

来自「cvnbmn,bjh,bnvbnvh vn vn vcvbcb」· C++ 代码 · 共 343 行

#include <iostream>

#include <conio.h>

#include <windows.h>     //显示矩阵时需要延时，这里有Sleep()函数。

using namespace std;

 

//接收键盘时使用

const enum Input { UP = 0x048, DOWN = 0x050, LEFT = 0x04b, RIGHT = 0x04d, ENTER = 0xd };

//扩展时判断方向使用

const int U = 0;

const int D = 1;

const int L = 2;

const int R = 3;

 


class ElemType {

private:

    int depth;        //当前节点的深度（就是距离初始节点有多远）

    int numWrong();   //有多少错位的数字

 

public:

 

    int maze[9];      //保存矩阵用

    ElemType* flag;   //指向根节点

    ElemType();       //创建初始节点

 

    ElemType(int,int,int,int,int,int,int,int,int); 

    bool operator ==(ElemType e) { 

 

 

       for(int i = 0; i < 9; i++)

           if(this->maze[i]!=e.maze[i])

              return false;

       return true;

    }

    void operator =(ElemType e) {

       for(int i = 0; i < 9; i++)

           this->maze[i] = e.maze[i];

       this->depth = e.depth;

       this->flag = e.flag;

       this->numWrong();

    }

    ElemType friend operator >>(ElemType source, int direct) {

//这个运算符的重载是对于L，R，U，D四个方向作出的移动

       ElemType result = source;

       int i = result.locate0();

       switch(direct) {

           case U: if(i < 6) {

result.maze[i] = result.maze[i+3];

result.maze[i+3] = 0;

} break;

           case D: if(i > 2) {

result.maze[i] = result.maze[i-3];

result.maze[i-3] = 0;

} break;

           case L: if(i%3 != 2) {

result.maze[i] = result.maze[i+1];

result.maze[i+1] = 0;

} break;

           case R: if(i%3 != 0) {

result.maze[i] = result.maze[i-1];

result.maze[i-1] = 0;

}

       }

       result.depth++;

       return result;

    }

    int locate0();      //确定0所在的位置，其余方法要调用


    bool isSuccess();   //判定当前节点是否是最终节点
//下面是评价函数

    int evaluate() { return depth + numWrong(); }

    void disrupt() {      //打乱初始矩阵

       // clrscr();

        this->print();

        int input;

        while((input=_getch()) != ENTER) {

            switch(input) {

                case UP:    *this = *this >> U; this->print(); break;

                case DOWN:  *this = *this >> D; this->print(); break;

                case LEFT:  *this = *this >> L; this->print(); break;

                case RIGHT: *this = *this >> R; this->print();

            }

        }

    }

    void print() {        //在屏幕中央显示矩阵

        for(int i = 0; i < 3; i++) {

            for(int j = 0; j < 3; j++) {

                gotoxy(36+j*3, 8+i);

                if(maze[i*3+j]!=0) cout <<'['<< maze[i*3+j] << ']';

                else cout << "   ";

            } cout << endl;

       }

        Sleep(200);

    }

}

 

void print(ElemType &e) { e.print(); }

 

ElemType null(0,0,0,0,0,0,0,0,0); //每个位置都是0，这是不存在的

 


#include "dso.h" 

typedef ElemType Status;



//接下来是搜索的操作。closed表仍然是野人传教士问题里使用过的Queuex队列；由于可能要随时删除open表里的任意一个节点，所以open表使用单链表，同时要有获得评价函数值最小的节点的位置的方法。

class LListx : public LList {

public:

    ElemType getMin() {

    //找出并返回评价函数值最小的节点，如果有多个相等的则返回第一个，如果有最终节点也返回。

       LNode* temp = L->next;

       ElemType e = temp->node;

       while(temp->next) {

           temp = temp->next;

           if( temp->node.evaluate() < e.evaluate() )

              e = temp->node;

       }

       temp = L->next;

       while(temp->next) {

           temp = temp->next;

           if( temp->node.evaluate()==e.evaluate() &&

               temp->node.isSuccess() )

              e = temp->node;

       }

       return e;

    }

    int locateMin() {

     //返回getMin()所得到的节点的位置，如果不存在返回INFEASIBLE。

       int count = 0;

       LNode* temp = L->next;

       while( temp && !(temp->node==LListx::getMin()) &&

        temp->node.evaluate()!=LListx::getMin().evaluate() ) {

           count++;

           temp = temp->next;

       }

       temp = NULL;

       if(count < LList::length()) return count; 

       return INFEASIBLE;

    }

};


//Answer表的实现方法与野人传教士问题类似。


class Answer : public Queue {

public:

    Answer(const ElemType original) {

       LListx open;

       Queuex closed;

       Stack temp;

       Status s1, s2;

      //以下是搜索算法：

       open.insert(original, open.length());

       while( !open.isEmpty() ) {

           s1 = open.erase(open.locateMin());

           closed.enqueue(s1);

           if( s1.isSuccess() ) {

              while(s1.flag != NULL) { temp.push(s1); s1 = *(s1.flag); }

              this->enqueue(original);

              while(!s1.isSuccess()) {

                   s1 = temp.pop(); this->enqueue(s1);

              }

              return;

           }

           for(int i = 0; i < 4; i++) {

              s2 = s1 >> i;

              if( !(s1==s2)) 

                  if(closed.locate(s2) == INFEASIBLE) {

                  s2.flag = closed.getTailPtr();

                  open.insert(s2, open.length());

              }

           }

       }

    }

//...

}