POJ2488 A Knight’s Journey


DFS裸题。注意这道题需要的输出的是字典序最先的方案,所以我们需要注意遍历顺序为[-1,-2][1,-2],[-2,-1],[2,-1],[-2,1],[2,1],[-1,2],[1,2]以保证答案字典序最先。

本题在切的时候出现了一些诡异的问题……
传送门:一些奇奇怪怪的错误

附AC代码。

#include <cstdio>
#include <cstring>

int cases,p,q,dirx[]={0,-1,1,-2,2,-2,2,-1,1},diry[]={0,-2,-2,-1,-1,1,1,2,2},tot;
bool use[30][30],flg;

struct point{
	int x,y;
}po[1000];

bool dfs(int targetx,int targety,int deep)
{
	if(deep==tot)
	{
		po[deep].x=targetx;
		po[deep].y=targety;
		flg=true;
		return true;
	}
	for(int i=1;i<=8;++i)
		if(targetx+dirx[i]>0&&targetx+dirx[i]<=p&&targety+diry[i]>0&&targety+diry[i]<=q&&!use[targetx+dirx[i]][targety+diry[i]])
		{
			if(flg) return false;
			use[targetx+dirx[i]][targety+diry[i]]=true;
			if(dfs(targetx+dirx[i],targety+diry[i],deep+1))
			{
				po[deep].x=targetx;
				po[deep].y=targety;
				return true;
			}
			use[targetx+dirx[i]][targety+diry[i]]=false;
		}
	return false;
}

int main()
{
	scanf("%d",&cases);
	for(int cnt=1;cnt<=cases;++cnt)
	{
		memset(use,false,sizeof use);
		flg=false;
		scanf("%d%d",&p,&q);
		tot=p*q;
		use[1][1]=true;
		dfs(1,1,1);
		printf("Scenario #%d:\n",cnt);
		if(flg) for(int i=1;i<=tot;++i) printf("%c%d",'A'+po[i].y-1,po[i].x);
		else printf("impossible");
		printf("\n\n");
	}
	return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - POJ2488 A Knight’s Journey


不骗了,不骗了。
A Simple OIer fighting tooth and nail.