2243:Knight Moves
文章目录
- 题目描述
- 思路
- 1. DFS
- 2. BFS
- 3. 动态规划
- 解题方法
- 1. DFS
- 2. BFS
- 3. 动态规划
题目描述
题目链接
翻译如下：
注：骑士移动是和象棋里的马一样走的是日字型
你的一个朋友正在研究旅行骑士问题 （TKP），你要找到最短的骑士步数封闭之旅，该游轮在棋盘上只访问一次给定的 n 个方格的每个方格。他认为问题中最困难的部分是确定两个给定方格之间的最小骑士移动次数，一旦你完成了这个任务，找到巡回赛就很容易了。
当然，您知道反之亦然。所以你让他写一个程序来解决“困难”的部分。
你的工作是编写一个程序，将两个方格 a 和 b 作为输入，然后确定从 a 到 b 的最短路线上的骑士移动次数。
输入
输入将包含一个或多个测试用例。每个测试用例由一行组成，其中包含两个方块，由一个空格分隔。正方形是由代表列的字母 （a-h） 和代表棋盘上行的数字 （1-8） 组成的字符串。
输出
对于每个测试用例，打印一行，上面写着“从 xx 到 yy 需要 n 个骑士动作”。
用例：
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
输出结果：
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
思路
这道题要求的就是一个坐标到另一个坐标的最短路径。
路径的求法可以是递归求解（DFS/BFS），也可以是图论求解（Floyd/Dijkstra）。下面我用DFS、BFS、动态规划分别求解这道题。
1. DFS
DFS算法又称深度搜索法，总而言之还是递归三部曲：返回值及传入参数/递归条件/终止条件
- 传入参数及返回值
传入起始坐标，不需要返回值，采用引用方法即可获得结果，用step[i][j]存从起始位置到i行j列的最短距离
void dfs(int x1,int y1,int result,vector<vector<int> > &step){}
- 递归条件
向四周递归的下一个坐标不超过最大范围，且为了找到最小距离，也要判断当前值是不是比已经存入的值大，如果比存入值还小就更新最短距离，然后接着向下递归
//判断当前结点坐标是否满足条件
if(x1<0||x1>7||y1<0||y1>7||step[x1][y1]<=result)return ;
//更新步数
step[x1][y1]=result;
//向下递归
for(int i=0;i<8;i++){
dfs(x1+row[i],y1+col[i],result+1,step);
}
- 终止条件
不满足条件时则终止当前循环
2. BFS
BFS算法又称广度搜索法，是从一个点一层一层向外扩散直至覆盖整个区域，需要用一个队列来暂存遍历的所有结点，方法和递归有所出入，细分应该算是迭代法。
- 用一个结构体存每个结点的左边信息以及到达该节点所需的路径长度
struct Node{
int x;//横坐标
int y;//纵坐标
int step;//所需最短路径长度
};
- 逐层遍历
先存入起始结点
void bfs(){
queue<Node> que;
Node cur,next;
cur.x=x1;cur.y=y1;cur.step=0;//当前所在坐标
que.push(cur);
}
- 取出队列头结点，以它为起始节点继续向四周遍历。如果遍历到终止结点则结束广搜；遍历到的结点最短路径在该起始节点的路径长度的基础上加1
while(!que.empty()){
cur=que.front();//取出头节点
que.pop();
if(cur.x==x2&&cur.y==y2){//已经到达终止位置，结束遍历
cout<<"To get from "<<a<<" to "<<b<<" takes "<<cur.step<<" knight moves."<<endl;
return;
}
for(int i=0;i<8;i++){
//继续向四周广搜
next.x=cur.x+row[i];
next.y=cur.y+col[i];
next.step=cur.step+1;
if(next.x<0||next.x>7||next.y<0||next.y>7)continue;//坐标不满足条件
if(next.step!=100){//满足要求的结点存入队列
next.step=cur.step+1;
que.push(next);
}
}
}
3. 动态规划
动态规划五部曲：
- dp数组及其下标含义
dp[i][j]:从初始位置到i行j列的最短距离 - 初始化
起始位置初始化为0，因为是求最短路径，其他位置的值必须保证能让路径被录入，所以初始化为一个较大的值，我初始化为100了 - 递推公式
因为dp[i][j]是可以由日字型一脚的任何一个坐标推导而来
dp[x][y]=min(dp[x][y],dp[i][j]+1) - 遍历顺序
我比较蠢，遍历我采用了四种方向，具体为什么我也暂时不太清楚，反正我自己写出来结果是对的，希望有大佬可以为了解答 - 打印dp数组
解题方法
1. DFS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
//八个移动方向
int row[8]={-2,-1,1,2,2,1,-1,-2};
int col[8]={1,2,2,1,-1,-2,-2,-1};
void dfs(int x1,int y1,int result,vector<vector<int> > &step){
//判断当前结点坐标是否满足条件
if(x1<0||x1>7||y1<0||y1>7||step[x1][y1]<=result)return ;
//更新步数
step[x1][y1]=result;
//向下递归
for(int i=0;i<8;i++){
dfs(x1+row[i],y1+col[i],result+1,step);
}
}
int main(){
string a,b;
while(cin>>a>>b){
vector<vector<int> > step(8,vector<int>(8,100));//记录到(i,j)格子的所需步数
//end的坐标
int y2=b[0]-'a';
int x2=b[1]-'1';
dfs(a[1]-'1',a[0]-'a',0,step);
cout<<"To get from "<<a<<" to "<<b<<" takes "<<step[x2][y2]<<" knight moves."<<endl;
}
}
2. BFS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
int row[8]={-2,-1,1,2,2,1,-1,-2};
int col[8]={1,2,2,1,-1,-2,-2,-1};
struct Node{
int x;//横坐标
int y;//纵坐标
int step;//所需最短路径长度
};
int x1,y1;//起始坐标
int x2,y2;//终止坐标
string a,b;
void bfs(){
queue<Node> que;
Node cur,next;
cur.x=x1;cur.y=y1;cur.step=0;//当前所在坐标
que.push(cur);
while(!que.empty()){
cur=que.front();//取出头节点
que.pop();
if(cur.x==x2&&cur.y==y2){//已经到达终止位置，结束遍历
cout<<"To get from "<<a<<" to "<<b<<" takes "<<cur.step<<" knight moves."<<endl;
return;
}
for(int i=0;i<8;i++){
//继续向四周广搜
next.x=cur.x+row[i];
next.y=cur.y+col[i];
next.step=cur.step+1;
if(next.x<0||next.x>7||next.y<0||next.y>7)continue;//坐标不满足条件
if(next.step!=100){//满足要求的结点存入队列
next.step=cur.step+1;
que.push(next);
}
}
}
}
int main(){
while(cin>>a>>b){
//1为起始结点，2为终止结点
x1=a[1]-'1';
y1=a[0]-'a';
x2=b[1]-'1';
y2=b[0]-'a';
bfs();
}
}
3. 动态规划
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int row[8]={-2,-1,1,2,2,1,-1,-2};
int col[8]={1,2,2,1,-1,-2,-2,-1};
int stx,sty,edx,edy;
int main(){
string a,b;
while(cin>>a>>b){
stx=a[1]-'1';
sty=a[0]-'a';
edx=b[1]-'1';
edy=b[0]-'a';
int dp[8][8];
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
dp[i][j]=100;
}
}
dp[stx][sty]=0;//起始位置所需步数为0
//从左到右从上到下遍历
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
for(int k=0;k<8;k++){
int x=i+row[k];
int y=j+col[k];
if(x<0||x>7||y<0||y>7||dp[i][j]==100)continue;
dp[x][y]=min(dp[x][y],dp[i][j]+1);
}
}
}
//从右到左从下到上遍历
for(int i=7;i>=0;i--){
for(int j=7;j>=0;j--){
for(int k=0;k<8;k++){
int x=i+row[k];
int y=j+col[k];
if(x<0||x>7||y<0||y>7||dp[i][j]==100)continue;
dp[x][y]=min(dp[x][y],dp[i][j]+1);
}
}
}
//从左到右从下到上遍历
for(int i=0;i<8;i++){
for(int j=7;j>=0;j--){
for(int k=0;k<8;k++){
int x=i+row[k];
int y=j+col[k];
if(x<0||x>7||y<0||y>7||dp[i][j]==100)continue;
dp[x][y]=min(dp[x][y],dp[i][j]+1);
}
}
}
//从右到左从上到下遍历
for(int i=7;i>=0;i--){
for(int j=0;j<8;j++){
for(int k=0;k<8;k++){
int x=i+row[k];
int y=j+col[k];
if(x<0||x>7||y<0||y>7||dp[i][j]==100)continue;
dp[x][y]=min(dp[x][y],dp[i][j]+1);
}
}
}
//输出结果
cout<<"To get from "<<a<<" to "<<b<<" takes "<<dp[edx][edy]<<" knight moves."<<endl;
}
}