#include <vector>
#include <queue>
#ifndef _SEARCHER_H_
#define _SEARCHER_H_

class HASH;
struct NODE{
	int status;    //狀態(tài)
	int step;      //步長(zhǎng)
	int val;       //估價(jià)值
	int father;    //父結(jié)點(diǎn)
	int zero;      //空格所在位置
};


const int MAXNODE = 182000;
extern HASH tree;
extern struct NODE open[MAXNODE];
extern int top;


class searcher{
protected:
	int ten[9];   //ten[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000}
	int swap[9][9];   //狀態(tài)轉(zhuǎn)換用數(shù)組
	int dis[9][9];    //兩數(shù)碼之間的距離
	int des[9];	      //目標(biāo)結(jié)點(diǎn)各個(gè)數(shù)碼所在位置
	int m_end;        //結(jié)束狀態(tài)
	int last_index;   //open表最后一個(gè)元素下標(biāo)
	int expanded;     //已擴(kuò)展的節(jié)點(diǎn)
	int inopen;       //仍在open表中的結(jié)點(diǎn)
	enum{NOANSWER, STOP, CANTFIND, SUCCESS}result;  //搜索結(jié)果
	int totalnode;   //搜索過(guò)的總節(jié)點(diǎn)數(shù) - 1。
	double P;  //外顯率  P = L / T;  L為路徑長(zhǎng)度， T為中間生成的節(jié)點(diǎn)總數(shù)。
	double B;  //有效分枝因數(shù) T = B * (B ^ L - 1) / (B - 1); 可二分求解。

public:
	
	virtual int search(int begin, int end, int &stop, int val = 0) = 0;  //-1無(wú)解，-2用戶終止，0找不到解，1有解
	virtual void getPath(std::vector<int> &vec);
	int reset(const int begin, const int end, int mode = 1);   //重置初始值，返回初始位置啟發(fā)值		
	int getnextstatus(const int status, const int zero, const int zero_to){   //獲取下一個(gè)狀態(tài)
		return status + swap[zero][zero_to] * (status / ten[zero_to] % 10);		
	}
	virtual CString getIntroduction() = 0;  //介紹
	virtual CString getResult();     //獲取搜索結(jié)果
	int getreverse(int status);  //逆序數(shù)	
	void getP(){  //獲得外顯率
		P = ( (double) open[last_index].step) / totalnode;
	}
	double getB();  //獲得有效分枝因數(shù)
	int getStep(){return open[last_index].step;}   //解步長(zhǎng)
	int getTotalnode(){return totalnode + 1;}   //總共生成節(jié)點(diǎn)數(shù)
};

class HASH{
protected:
	struct Node{
		int data;	
		struct Node* next;
	};
	const static int MAXSIZE= 70001, ALL = 182000;	
	int ID;
	struct Node *hash[MAXSIZE], node[ALL];
public:
	bool add(const int m_data);
	void reset(){   //重置哈希表
		memset(hash, 0, sizeof(hash) );
		ID = 0;
	}
};

const int dir_count[] = {2, 3, 2, 3, 4, 3, 2, 3, 2};
const int dir[][4] = {
	{1, 3, 0, 0},
	{0, 2, 4, 0},
	{1, 5, 0, 0},
	{0, 4, 6, 0},
	{1, 3, 5, 7},
	{2, 4, 8, 0},
	{3, 7, 0, 0},
	{4, 6, 8, 0},
	{5, 7, 0, 0}
};



#endif