P2324 [SCOI2005]骑士精神(IDA*)

思路:不是动骑士,而是动空格。只能动15次,证明搜索树的高的确定的,考虑IDA解决 IDA能很好地解决一些搜索中有上界的情况 大概就是搞一个估值函数,然后当前情况+估价函数>限制的情况直接剪掉这个情况 所以IDA*执行的时候需要枚举一下上界。然后本题的估价函数表现为当前局面和目标相比还差了多少个步数. 每次交换最好的情况就是黑白直接对换。那样消除不同格子（2个）最快的步数也是2.也就是一个步数消除一个不同点,这是最好的情况.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
int mp[7][7];
//0是白子,1是黑子,2个空格
int ans[7][7]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0}
};
int n =5;
int flag = -1;
int func(){
	int dif = 0;
	for(int i=1;is;
			for(int j=1;j