#include "stdafx.h"
#include "bdfs.h"


HASH_BDFS tree_bdfs;

CString BDFS::getIntroduction(){
	CString intro = "有界深度優(yōu)先搜索\r\n\r\n"
					"搜索時(shí)優(yōu)先搜索子樹(shù)，"
					"但是不能保證找到最優(yōu)解。"
					"由于有深度限制，所以可以保證不會(huì)陷入一棵子樹(shù)內(nèi)出不來(lái)，"
					"但是卻有可能因?yàn)樯疃炔粔蚨也坏浇狻?quot;;
	return intro;
}

CString BDFS::getResult(){
	CString str;
	str = searcher::getResult();
	str += "\r\n";
	char ss[20];
	sprintf(ss, "當(dāng)前深度限制：%d", maxstep);
	return (str += ss);	
}



int BDFS::search(int begin, int end, int &stop, int val){
	if((getreverse(begin) & 1) != (getreverse(end) & 1) ){  //逆序數(shù)不一樣，無(wú)解
		result = NOANSWER;
		return -1;
	}
	maxstep = val;
	std::vector<int> Q;
	result = SUCCESS;
	open[0].father = -1;
	open[0].step = 0;
	open[0].status = begin;
	int index, tmp;
	for(index = 0, tmp = begin; tmp % 10; ++index, tmp /= 10);
	open[0].zero = index;
	Q.push_back(top = 0);
	tree_bdfs.reset();
	tree_bdfs.add(begin, 0, 0);
	reset(begin, end); //初始轉(zhuǎn)換信息
	while(!stop && !Q.empty()){
		index = Q.back();
		Q.pop_back();		
		if(open[index].status == end){
			last_index = index;
			totalnode = top;
			expanded = top + 1 - Q.size();
			inopen = Q.size();
			return 1;
		}
		if(open[index].step >= val) continue;
		int zero = open[index].zero;
		for(int i = 0; i < dir_count[zero]; i++){				
			int tmp = getnextstatus(open[index].status, zero, dir[zero][i]);
			int newindex = tree_bdfs.add(tmp, top + 1, open[index].step + 1);
			if(newindex == 0){
				open[++top].father = index;
				open[top].status = tmp;
				open[top].step = open[index].step + 1;
				open[top].zero = dir[zero][i];
				Q.push_back(top);
			}else if(newindex > 0){
				open[newindex].father = index;
				open[newindex].step = open[index].step + 1;			
				Q.push_back(newindex);
			}
		}
	}

	expanded = top + 1 - Q.size();
	inopen = Q.size();
	if(stop){
		result = STOP;
		return -2;
	}
	result = CANTFIND;
	return 0;
}