#include "stdafx.h"
#include "ida.h"


extern HASH tree;

CString IDA::getResult(){
	CString str = searcher::getResult();
	if(result == SUCCESS){
		char ss[50];
		sprintf(ss, "\r\n迭代時(shí)最多擴(kuò)展出%d個(gè)結(jié)點(diǎn)", top + 1);
		str += ss;
	}
	return str;
}

CString IDA::getIntroduction(){
	CString intro = "IDA*搜索算法\r\n\r\n"
					"是基于重復(fù)式深度優(yōu)先的A*算法，忽略所有f值大于深度限制的結(jié)點(diǎn)。"
					"由于逐步加大限制，能保證找到最優(yōu)解。啟發(fā)函數(shù)采"
					"用所有圖片到達(dá)目的地的曼哈頓距離之和";
	return intro;
}


int IDA::search(int begin, int end, int &stop, int val){
	if((getreverse(begin) & 1) != (getreverse(end) & 1) ){  //逆序數(shù)不一樣，無(wú)解
		result = NOANSWER;
		return -1;
	}
	std::queue<int> Q;
	result = SUCCESS;
	open[0].father = -1;
	open[0].step = 0;
	open[0].status = begin;
	int index, tmp, limit;
	for(index = 0, tmp = begin; tmp % 10; ++index, tmp /= 10);
	open[0].zero = index;		
	open[0].val = reset(begin, end); //初始轉(zhuǎn)換信息	
	limit = open[0].val - 1;
	totalnode = 0;
	while(!stop){
		Q.push(top = 0);
		limit ++;
		tree.reset();
		tree.add(begin);
		do{
			index = Q.front();
			Q.pop();
			if(open[index].status == end){
				last_index = index;
				totalnode += top;
				expanded = totalnode + 1 - Q.size();
				inopen = Q.size();
				return 1;
			}
			if(limit < open[index].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]);
				if(tree.add(tmp) ){
					open[++top].father = index;
					open[top].status = tmp;
					open[top].step = open[index].step + 1;
					open[top].zero = dir[zero][i];
					open[top].val = getval(tmp, (open[index].val - open[index].step), zero, dir[zero][i]) 
								+ open[top].step;
					Q.push(top);
				}
			}
		}while(!stop && !Q.empty() );
		totalnode += top + 1;
	}

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