NOI - OpenJudge - 2.5基本算法之搜索 - 1490:A Knight‘s Journey - 超详解析（含AC代码）
点赞关注吧~
1490:A Knight's Journey
总时间限制:
1000ms
内存限制:
65536kB
描述
Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?
Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
输入
The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
输出
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
样例输入
3 1 1 2 3 4 3
样例输出
Scenario #1: A1 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4
来源
TUD Programming Contest 2005, Darmstadt, Germany
翻译
背景 这位骑士厌倦了一遍又一遍地看到相同的黑白方块，决定开始一场环游世界的旅程。骑士每次移动时，向一个方向走两个方块，然后垂直于此再走一个方块。这位骑士的世界是他所生活的棋盘。我们的骑士生活在一个比标准的8*8棋盘面积小的棋盘上，但它仍然是矩形的。您能帮助这位冒险的骑士制定旅行计划吗？
问题 找到一条路径，使得骑士访问每个方块一次。骑士可以从棋盘的任意一个方块开始并结束。
输入输出
这段文本描述了一个输入输出规范，要求实现一个程序，根据输入的测试用例，在国际象棋棋盘上使用骑士的走法找出一条经过所有方格的最短路径，并按照字典序输出路径。如果不存在这样的路径，则输出"impossible"。
具体要求如下：
- 输入包含多个测试用例，每个测试用例包含两个正整数 p 和 q，表示一个 p*q 的国际象棋棋盘，其中 p 表示横向的不同方格数，q 表示纵向的不同方格数，且满足 1 <= p * q <= 26。
- 输出对每个测试用例，首先输出一行 "Scenario #i:"，其中 i 表示测试用例的序号，从 1 开始。
- 然后输出一行，包含经过所有方格的最短路径，按照字典序输出，每个方格用一个大写字母加一个数字表示。
- 如果不存在满足条件的路径，则输出一行 "impossible"。
希望这样的翻译对您有所帮助。如果需要进一步解释或有其他问题，请随时告诉我。
走法
在国际象棋中，骑士的移动方式是“日”字形，即每次移动两格沿一个方向，然后再移动一格与之垂直的方向。这种移动方式使得骑士在棋盘上的路径呈现出 L 字形。骑士可以沿着横向或纵向移动两格，然后再沿着垂直于之前移动方向的方向移动一格，或者沿着纵向或横向移动一格，然后再沿着垂直于之前移动方向的方向移动两格。
这种特殊的移动方式使得骑士在棋盘上可以覆盖到每一个方格，而不会重复经过同一个方格。因此，要找到一条路径，使得骑士访问每个方格一次，可以利用骑士的 L 字形移动规则，按照特定顺序遍历整个棋盘。可以通过深度优先搜索（DFS）或者回溯算法来找到这样一条路径。
这里是国际象棋中骑士的走法示意图：
1 2 3 4 5 6 7 8
1 . . . . .
2 . . . . .
3 . . . . .
4 . . N . .
5 . . . . .
6 . . . . .
7 . . . . .
8 . . . . .在上面的示意图中，N 代表骑士的位置，骑士可以移动到示意图中的任何一个点。骑士的移动路径将形成 L 字形，即每次移动两格沿一个方向，然后再移动一格与之垂直的方向，或者每次移动一格沿一个方向，然后再移动两格与之垂直的方向。
代码及题解
标准代码
#include<iostream>
#include<cstring>
using namespace std;
bool vis[30][30], flag;
int visnum, p, q;
char path[60];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
void dfs(int num,int x,int y)
{
if(num==visnum)
{
for(int i=0;i<2*visnum;i++)
cout<<path[i];
cout<<endl<<endl;
flag=true;
return ;
}
for(int i=0;i<8&&!flag;i++)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>0&&yy>0&&xx<=q&&yy<=p&&!vis[xx][yy])
{
vis[xx][yy]=true;
path[2*num]='A'+xx-1;
path[2*num+1]='0'+yy;
dfs(num+1,xx,yy);
vis[xx][yy]=false;
}
}
}
int main()
{
int n;
cin>>n;
int m=1;
while(n--)
{
cout<<"Scenario #"<<m++<<":"<<endl;
cin>>p>>q;
memset(vis,false,sizeof(vis));
vis[1][1]=true;
visnum=p*q;
flag=false;
path[0]='A'; path[1]='1';
dfs(1,1,1);
if(!flag)
cout<<"impossible"<<endl<<endl;
}
return 0;
}手写代码
#include <bits/stdc++.h>
using namespace std;
int t;//多测
int p,q;//p->列 q->行
bool visited[30][30];
bool flag;
int movex[8]={-2,-2,-1,-1,1,1,2,2};
int movey[8]={-1,1,-2,2,-2,2,-1,1};
/* 位移增量
上下搭配 */
int turn=1;
char res[60];
void dfs(int num,int x,int y){
visited[x][y]=true;
if(num==p*q){//走完了
for(int i=0;i<p*q*2;i++){
cout<<res[i];
}
cout<<endl<<endl;
flag=true;
return ;
}
else{
for(int i=0;i<8&&!flag;i++){
int X=x+movex[i];
int Y=y+movey[i];
if(!visited[X][Y]&&((X>0&&X<=q)&&(Y>0&&Y<=p))){
res[num*2]='A'+X-1;
res[num*2+1]='0'+Y;
visited[X][Y]=true;
dfs(num+1,X,Y);
visited[X][Y]=false;
}
}
}
return ;
}
int main(){
cin>>t;
while(t--){
cin>>p>>q;
memset(visited,false,sizeof(visited));
visited[1][1]=true;
flag=false;
res[0]='A';
res[1]='1';
cout<<"Scenario #"<<turn<<":"<<endl;
dfs(1,1,1);
if(!flag){
cout<<"impossible"<<endl<<endl;
}
turn++;
}
return 0;
}原文地址：https://blog.csdn.net/2301_76723927/article/details/137368208
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！