BZOJ.1085.[SCOI2005]骑士精神(迭代加深搜索)

最小步数这类，适合用迭代加深搜索。

用空格走代替骑士。

搜索时记录上一步防止来回走。

不需要每次判断是否都在位置，可以计算出不在对应位置的骑士有多少个。而且每次复原一个骑士至少需要一步。

空格是不计算未复原骑士数的。

//820kb	84ms

#include <cstdio>

#include <cstring>

#include <algorithm>

#define n (5)

typedef long long LL;

const int way_x[9]={1,1,2,2,-2,-2,-1,-1},way_y[9]={2,-2,1,-1,1,-1,2,-2};

const int End[6][6]=

{{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 mp[7][7];

char s[10];

bool DFS(int x,int y,int left,int sum,int las)

{

	if(sum>left) return 0;

	if(!sum) return 1;

	for(int xn,yn,res,i=0; i<8; ++i)

		if(i!=7-las&&(xn=x+way_x[i])>0&&(yn=y+way_y[i])

>0&&xn<=n&&yn<=n)

		{

			res=sum;

			if(mp[xn][yn]==End[xn][yn]) ++res;

			std::swap(mp[x][y],mp[xn][yn]);

			if(mp[x][y]==End[x][y]) --res;

			bool f=DFS(xn,yn,left-1,res,i);

			if(f) return 1;

			std::swap(mp[x][y],mp[xn][yn]);

		}

	return 0;

}

int main()

{

	int T,sx,sy,init; scanf("%d",&T);

	while(T--)

	{

		for(int i=1; i<=n; ++i)

		{

			scanf("%s",s+1);

			for(int j=1; j<=n; ++j)

				if(s[j]!='*') mp[i][j]=s[j]-'0';

				else mp[i][j]=2,sx=i,sy=j;

		}

		init=0;

		for(int i=1; i<=n; ++i)

			for(int j=1; j<=n; ++j)

				if(mp[i][j]!=End[i][j]) ++init;//init:至少需要

多少步。

		if(sx!=3||sy!=3) --init;//空格不计算未复原骑士数。

//		printf("init:%d\n",init);

		for(int dep=init; ; ++dep)

			if(dep==16) {puts("-1"); break;}

			else if(DFS(sx,sy,dep,init,8)) {printf("%d\n",dep); 

break;}

	}

	return 0;

}

附上sb哈希的代码吧。。真是学傻了。

#include <map>

#include <set>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define n (5)

typedef long long LL;

const int way_x[9]={1,1,2,2,-1,-1,-2,-2},way_y[9]={2,-2,1,-1,2,-2,1,-1};

const int End[6][6]=

{{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 mp[7][7];

short Ans;

char s[10];

std::map<LL,short> vis;

std::set<LL> st;

bool Victory()

{

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j)

			if(mp[i][j]!=End[i][j]) return 0;

	return 1;

}

LL Encode()

{

	LL res=0;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j) res=res*3+mp[i][j];

//	if(Victory()){

//		printf("%I64d:\n",res);

//		for(int i=1; i<=n; ++i,putchar('\n'))

//			for(int j=1; j<=n; ++j) printf("%d ",mp[i][j]);

//	}

	return res;

}

short DFS(int x,int y,short step,LL s)

{

	if(step>15) return 16;

	if(Ans<=step) return 17;

	if(x==3&&y==3&&Victory()) {Ans=std::min(Ans,step); return step;}

	short res=17; LL ss;

	for(int xn,yn,i=0; i<8; ++i)

		if((xn=x+way_x[i])>0&&(yn=y+way_y[i])>0&&xn<=n&&yn<=n)

		{

			std::swap(mp[x][y],mp[xn][yn]);

			ss=Encode();

			if(!st.count(ss))

				st.insert(ss),res=std::min(res,DFS(xn,yn,step+1,ss)),st.erase(ss);

			std::swap(mp[x][y],mp[xn][yn]);

		}

	return res;

}

int main()

{

	int T,sx,sy; scanf("%d",&T);

	while(T--)

	{

		Ans=16, st.clear(), vis.clear();

		for(int i=1; i<=n; ++i)

		{

			scanf("%s",s+1);

			for(int j=1; j<=n; ++j)

				if(s[j]!='*') mp[i][j]=s[j]-'0';

				else mp[i][j]=2,sx=i,sy=j;

		}

		LL s=Encode();

		st.insert(s);

		DFS(sx,sy,0,s);

		printf("%d\n",Ans<=15?Ans:-1);

	}

	return 0;

}

巴特西

BZOJ.1085.[SCOI2005]骑士精神(迭代加深搜索)

最新文章

热门文章