欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2488 A Knight's Journey(DFS、记录路径)

程序员文章站 2024-02-11 17:18:52
...

题目链接:点击这里
POJ 2488 A Knight's Journey(DFS、记录路径)
POJ 2488 A Knight's Journey(DFS、记录路径)
POJ 2488 A Knight's Journey(DFS、记录路径)The knight can start and end on any square of the board. 被这句吓到了,弄了 pqp*q 次BFS,搞了一个小时也没搞出来。

参考链接:https://blog.csdn.net/lyhvoyage/article/details/18355471

大致题意:给出一个 ppqq 列的国际棋盘,马可以从任意一个格子开始走,问马能否不重复的走完所有的棋盘。如果可以,输出按字典序排列最小的路径。打印路径时,列用大写字母表示(AA 表示第一列),行用阿拉伯数字表示(从 11 开始),先输出列,再输出行。

分析:如果马可以不重复的走完所有的棋盘,那么它一定可以走到 A1A1 这个格子。所以我们只需从 A1A1 这个格子开始搜索,就能保证字典序是小的;除了这个条件,我们还要控制好马每次移动的方向,控制方向时保证字典序最小(即按照下图中格子的序号搜索)。控制好这两个条件,直接从A1开始深搜就行了。

POJ 2488 A Knight's Journey(DFS、记录路径)
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

const int X[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int Y[8] = {-2, -2, -1, -1, 1, 1, 2, 2};

int row, col, path[30][2];
bool vis[30][30], flag;

void DFS(int x, int y, int idx)
{
	path[idx][0] = x;
	path[idx][1] = y;
	
	if(idx==row*col)
	{
		flag = true;
		return;
	}
	
	for(int i = 0; i < 8; i++)
	{
		int newx = x + X[i];
		int newy = y + Y[i];
		if(newx>=1&&newx<=row&&newy>=1&&newy<=col&&!vis[newx][newy]&&!flag)
		{
			vis[newx][newy] = true;
			DFS(newx, newy, idx+1);
			vis[newx][newy] = false;
		}
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	for(int k = 1; k <= t; k++)
	{
		scanf("%d%d", &row, &col);
		
		flag = false;
		for(int i = 1; i <= row; i++)
			for(int j = 1; j <= col; j++)
				vis[i][j] = false;
		
		printf("Scenario #%d:\n", k);
		vis[1][1] = true;
		DFS(1,1,1);
		if(flag)
		{
			for(int i = 1; i <= row*col; i++)
				printf("%c%d", 'A'+path[i][1]-1, path[i][0]);
			printf("\n");
		}
		else
			printf("impossible\n");
		if(k<t)	printf("\n");
	}
	return 0;
}
相关标签: DFS