B - DFS A Knight's Journey

程序员文章站 2024-02-11 17:09:40

...

题目

骑士无聊一次又一次看到相同的黑白方块，因此决定
环游世界。每当骑士移动时，它在一个方向上是两个正方形，而垂直于此方向的正方形则是一个正方形。骑士的世界就是他赖以生存的棋盘。我们的骑士生活在棋盘上，棋盘的面积比普通的8 * 8棋盘小，但它仍然是矩形的。您可以帮助这个冒险的骑士制定旅行计划吗？
B - DFS A Knight's Journey
找到一条路径，使骑士可以拜访每个广场一次。骑士可以在棋盘的任何正方形上开始和结束。

Input

输入在第一行中以正整数n开头。以下各行包含n个测试用例。每个测试用例都由一条带有两个正整数p和q的单行组成，因此1 <= p , q <=26。这表示ap * q棋盘，其中p描述了多少个不同的平方号1，2，3，…，p存在，q描述存在多少个不同的正方形字母。这些是拉丁字母的前q个字母：A 、B…

Output

每个方案的输出都以包含“方案#i：”的行开头，其中i是从1开始的方案编号。然后打印一行，按字典顺序，第一个路径通过骑士移动来访问棋盘的所有正方形用空行。应通过合并访问的正方形的名称在一行上给出路径。每个正方形名称均由大写字母后跟数字组成。
如果不存在这样的路径，则应在单行上输出“inpossible”。

Sample Input

3
1 1
2 3
4 3

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 手 ~ 动 ~ 分 ~ 割~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

思路：

很简单的一道搜索，数据量也很小（8*8），方心大胆地用DFS。

一个简单思路：

遍历棋盘的每一个格子作为起点开始跳，向八个方向分别蹦跶，将路径都存储下来，最后排序求出字典序最小解。
这样虽然不会超时 ~~（数据实在太水）~~ ，但是过于复杂 ~~（像我这种懒人坚决不会采用）~~。

更优的思路：

遍历棋盘的每一个格子作为起点开始跳，既然要让字典序最小，我们可以规定马从当前位置(x,y)向八个方向的遍历顺序，不难得出最小顺序为（x-1,y-2）,(x+1,y-2)…(x+1,y+2)。
这样可以保证每次遍历都从最小的情况考虑，节约了大量时间，不过还是太复杂 ~~（懒癌晚期患者）~~

更更优的思路：

如果能遍历棋盘，那么马必然经过A1点，很明显A1开头时字典序最小，所以我们只需从A1开始遍历即可，第一次找到的答案即为正确答案，省去了遍历全部棋盘的无脑时间。

代码如下

struct node
{
	int x,y;
}ans[900]; //ans数组存储路径

int T,n,m,k=1;
bool flag=0;//标记是否已经找到最优解
bool mp[30][30];//记录棋盘格点是否被遍历
int go[2][8]={{-1,1,-2,2,-2,2,-1,1},{-2,-2,-1,-1,1,1,2,2}};//最优遍历顺序

做好了准备，骑士同学开始快乐遍历！

void DFS(int x,int y,int step)//x，y表示当前遍历点的坐标，step记录遍历的步数（即已经遍历的格数）
{
	if(step==n*m)//如果遍历格数等于总格数（遍历完成）
	{
		for(int i=1;i<=step;i++)
		{
			cout<<char(ans[i].y+'A'-1)<<ans[i].x;
		}
		flag=1;//找到了！
		return ;
	}
	for(int i=0;i<8;i++)//朝八个方向蹦跶
	{
		int xx=x+go[0][i];
		int yy=y+go[1][i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!mp[xx][yy])//判断是否越界及是否已被遍历
		{
			ans[step+1].x=xx;
			ans[step+1].y=yy;//存入结果路径
			mp[xx][yy]=1;//落子并标记
			DFS(xx,yy,step+1);
			if(flag) return ;//如果已经有最优解直接结束
			mp[xx][yy]=0;//路堵死了走不通？不要怕，反手给个悔棋（chao ji jia bei）
		}
	}
}

主函数：

int main()
{
	int num=0;
	cin>>T;
	while(T--)
	{
		memset(mp,0,sizeof mp);//注意清零
		if(num!=0) cout<<"\n\n";//巨坑的换行
		num++;//记录组数
		cin>>n>>m;
		cout<<"Scenario #"<<num<<":\n";
		mp[1][1]=1;
		ans[1].x=1;
		ans[1].y=1;
		DFS(1,1,1);//直接从A1遍历
		if(!flag)//如果无解
			cout<<"impossible";
		flag=0;//注意清零
	}
}