/*?αβ剪枝?+?按層數(shù)多層搜索?+?論文估值?*/
#include?
#include?
#include?
#include??
#define?MAX_VAL?65000
#define?MIN_VAL?-65000
using?namespace?std;
/*
2
-1?-1?-1?-1?-1?-1
5?0?5?6?2?3
7?5?4?2?7?5
*/
int?n;
double?val0;
int?enddeep;?
int?a[8][8]={0};?//a現(xiàn)在棋盤(pán)?/*空格為0?我方棋子為1?對(duì)方棋子為2?障礙為-1*/
int?mx[4]my[4]dx[4]dy[4];//我方和敵方的坐標(biāo)?
int?sx[8]={10110-1-1-1};
int?sy[8]={11-10-110-1};
int?ansx1ansx2ansx3ansy1ansy2ansy3;

int?create（）?//?重建現(xiàn)在的棋盤(pán)到a?保存敵我坐標(biāo)到?mx?my?dx?dy?
{
	cin>>n;
	if（n<12）?enddeep=1;
	else?if（n<18）?enddeep=2;
	else?enddeep=3;
	int?x1y1x2y2x3y3;
	cin>>x1>>y1>>x2>>y2>>x3>>y3;
	if（x1==-1）
	{
		if（n==1）
		{
			cout<<“5?0?5?6?2?3“;
			exit（0）;
		}?
		a[2][0]=a[5][0]=a[0][2]=a[7][2]=1;
		a[0][5]=a[7][5]=a[2][7]=a[5][7]=2;
	}
	else
	{
		a[2][0]=a[5][0]=a[0][2]=a[7][2]=2;
		a[0][5]=a[7][5]=a[2][7]=a[5][7]=1;
		a[x2][y2]=a[x1][y1];
		a[x1][y1]=0;
		a[x3][y3]=-1;?
	}
	for（int?i=1;i<=n*2-2;i++）
	{
		cin>>x1>>y1>>x2>>y2>>x3>>y3;
		a[x2][y2]=a[x1][y1];
		a[x1][y1]=0;
		a[x3][y3]=-1;
	}
	int?wlink=0dlink=0;
	for（int?i=0;i<8;i++）
	for（int?j=0;j<8;j++）
	{
		if（a[i][j]==1）
		{
			mx[wlink]=i;
			my[wlink]=j;
			wlink++;
		}
		if（a[i][j]==2）
		{
			dx[dlink]=i;
			dy[dlink]=j;
			dlink++;
		}
	}
}
int?putout（）?//?debug輸出棋盤(pán)?
{
	for（int?i=0;i<=7;i++）
	{
		cout<<“?????“;
		for（int?j=0;j<=7;j++）
		{
			if（a[j][i]==1）?cout<<“M“;
			else?if（a[j][i]==2）?cout<<“D“;
			else?if（a[j][i]==-1）?cout<<“x“;
			else?cout<<“.“;
		}
		cout<	}
}
int?isout（int?xint?y）//?坐標(biāo)x.y是否越界?如果越界return?1?
{
	if（x<0||x>7||y<0||y>7）?return?1;
	else?return?0;
}
////////////////////////////////////////估值?
int?myking[8][8]diking[8][8]myqueen[8][8]diqueen[8][8]mm;
int?bj[8][8];
int?queuex[65]queuey[65]qdeep[65]topend;

double?value（）
{
	for（int?i=0;i<8;i++）
	for（int?j=0;j<8;j++）
	{
		myking[i][j]=diking[i][j]=myqueen[i][j]=diqueen[i][j]=MAX_VAL;
	}
	double?t1=0t2=0p1=0p2=0m=0;
	for（int?z=0;z<4;z++）
	{
		memset（bj0sizeof（bj））;
		top=0;
		end=1;
		queuex[0]=mx[z];
		queuey[0]=my[z];
		qdeep[0]=0;
		bj[mx[z]][my[z]]=1;
		while（top!=end）
		{
			int?x=queuex[top];
			int?y=queuey[top];
			int?deep=qdeep[top];
			myking[x][y]=min（myking[x][y]deep）;
			for（int?i=0;i<8;i++）
			{
				if（isout（x+sx[i]y+sy[i]））?continue;
				if（bj[x+sx[i]][y+sy[i]]）?continue;
				if（a[x+sx[i]][y+sy[i]]）?continue;
				queuex[end]=x+sx[i];
				queuey[end]=y+sy[i];
				qdeep[end]=deep+1;
				bj[x+sx[i]][y+sy[i]]=1;
				end++;
			}
			top++;
		}
		myking[mx[z]][my[z]]=MAX_VAL;
	}
	for（int?z=0;z<4;z++）
	{
		memset（bj0sizeof（bj））;
		top=0;
		end=1;
		queuex[0]=dx[z];
		queuey[0]=dy[z];
		qdeep[0]=0;
		bj[dx[z]][dy[z]]=1;
		while（top!=end）
		{
			int?x=queuex[top];
			int?y=queuey[top];
			int?deep=qdeep[top];
			diking[x][y]=min（diking[x][y]deep）;
			for（int?i=0;i<8;i++）
			{
				if（isout（x+sx[i]y+sy[i]））?co