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算法又称深度搜索法，总而言之还是递归三部曲：返回值及传入参数/递归条件/终止条件

  1. 传入参数及返回值
    传入起始坐标，不需要返回值，采用引用方法即可获得结果，用step[i][j]存从起始位置到i行j列的最短距离
	void dfs(int x1,int y1,int result,vector<vector<int> > &step){}
  1. 递归条件
    向四周递归的下一个坐标不超过最大范围，且为了找到最小距离，也要判断当前值是不是比已经存入的值大，如果比存入值还小就更新最短距离，然后接着向下递归
	//判断当前结点坐标是否满足条件 
	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); 	
	}
  1. 终止条件
    不满足条件时则终止当前循环

2. BFS

BFS算法又称广度搜索法，是从一个点一层一层向外扩散直至覆盖整个区域，需要用一个队列来暂存遍历的所有结点，方法和递归有所出入，细分应该算是迭代法。

  1. 用一个结构体存每个结点的左边信息以及到达该节点所需的路径长度
struct Node{
	int x;//横坐标
	int y;//纵坐标
	int step;//所需最短路径长度
};
  1. 逐层遍历
    先存入起始结点
void bfs(){
	queue<Node> que; 
	Node cur,next;
	cur.x=x1;cur.y=y1;cur.step=0;//当前所在坐标 
	que.push(cur);  
}
  1. 取出队列头结点，以它为起始节点继续向四周遍历。如果遍历到终止结点则结束广搜；遍历到的结点最短路径在该起始节点的路径长度的基础上加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. 动态规划

动态规划五部曲：

  1. dp数组及其下标含义
    dp[i][j]:从初始位置到i行j列的最短距离
  2. 初始化
    起始位置初始化为0，因为是求最短路径，其他位置的值必须保证能让路径被录入，所以初始化为一个较大的值，我初始化为100了
  3. 递推公式
    因为dp[i][j]是可以由日字型一脚的任何一个坐标推导而来
    dp[x][y]=min(dp[x][y],dp[i][j]+1)
  4. 遍历顺序
    我比较蠢，遍历我采用了四种方向，具体为什么我也暂时不太清楚，反正我自己写出来结果是对的，希望有大佬可以为了解答
  5. 打印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;
	}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/210517.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

结合贝叶斯定理浅谈商业银行员工异常行为排查

结合贝叶斯定理浅谈商业银行员工异常行为排查

1.贝叶斯定理的数学表达 贝叶斯方法依据贝叶斯定理。关于贝叶斯定理解释如下&#xff1a;首先我们设定在事件B条件下&#xff0c;发生事件A的条件概率&#xff0c;即 &#xff0c;从数学公式上&#xff0c;此条件概率等于事件A与事件B同时发生的概率除以事件B发生的概率。 上述…
阅读更多...
VUE语法-(readonly的用法)将数据设置成只读模式

VUE语法-(readonly的用法)将数据设置成只读模式

1、功能概述 在Vue中定义一个变量&#xff0c;这个变量的值不允许被修改&#xff0c;核心是通过readonly设置成只读。 如果不会使用ref和reactive响应式数据参考如下博客&#xff1a; https://blog.csdn.net/tangshiyilang/article/details/134701103 2、具体实现 如下案例…
阅读更多...
轻量级万物分割SAM模型——MobileSAM安装实测摘要

轻量级万物分割SAM模型——MobileSAM安装实测摘要

目录 0、前言1、准备工作安装python环境说明安装说明 运行测试app安装依赖修改代码 2、实际测试效果自带图片测试其它图片测试1其它图片测试2 总结 0、前言 本文将介绍一种轻量级万物分割SAM模型——MobileSAM的安装和实测情况。SAM是meta公司的一种图像分割大模型&#xff0c…
阅读更多...
摩根士丹利：人工智能推动增长

摩根士丹利：人工智能推动增长

摩根士丹利&#xff08;NYSE&#xff1a;MS&#xff09;将人工智能战略整合到其财富管理业务中&#xff0c;标志着竞争性金融格局迈出了变革性的一步。该公司的人工智能计划&#xff0c;包括与 OpenAI 合作开发人工智能聊天机器人&#xff0c;促进了其财富部门的显着增长。值得…
阅读更多...
VSCode 开发C/C++实用插件分享——codegeex

VSCode 开发C/C++实用插件分享——codegeex

VSCode 开发C/C实用插件分享——codegeex 一、codegeex 一、codegeex CodeGeeX 智能编程助手是一款编程插件&#xff0c;CodeGeeX支持多种主流IDE&#xff0c;如VS Code、IntelliJ IDEA、PyCharm、Vim等&#xff0c;同时&#xff0c;支持Python、Java、C/C、JavaScript、Go等多…
阅读更多...
C++学习之路（十六）C++ 用Qt5实现一个工具箱（为屏幕颜色提取功能增加一个点击复制的功能）- 示例代码拆分讲解

C++学习之路（十六）C++ 用Qt5实现一个工具箱（为屏幕颜色提取功能增加一个点击复制的功能）- 示例代码拆分讲解

上篇文章&#xff0c;我们用 Qt5 实现了在小工具箱中添加了《颜色代码转换和屏幕颜色提取功能》功能。今天我们把屏幕颜色提取的功能再扩展一下&#xff0c;让它可以点击复制吧。下面我们就来看看如何来规划开发这样的小功能并且添加到我们的工具箱中吧。 老规矩&#xff0c;先…
阅读更多...
CKafka 一站式搭建数据流转链路，助力长城车联网平台降低运维成本

CKafka 一站式搭建数据流转链路，助力长城车联网平台降低运维成本

关于长城智能新能源 长城汽车是一家全球化智能科技公司&#xff0c;业务包括汽车及零部件设计、研发、生产、销售和服务&#xff0c;旗下拥有魏牌、哈弗、坦克、欧拉及长城皮卡。2022年&#xff0c;长城汽车全年销售1,067,523辆&#xff0c;连续7年销量超100万辆。长城汽车面向…
阅读更多...
mysql手动事务

mysql手动事务

目录 &#x1f680;&#x1f680; 简要 手动事务使用案例 事务的特性 事务的隔离级别 脏读 不可重复读 幻读 查看事务隔离级别 设置隔离级别 &#x1fae1;&#x1fae1; 简要 mysq事务是自动提交的, 例如insert, update语句等 如下: 想要手动设置mysql事务就需…
阅读更多...
操作系统导论——第36章 I/O设备

操作系统导论——第36章 I/O设备

1. 系统架构 之所以使用分层&#xff0c;这是由于成本和效率之间的平衡 2. 标准设备 接口&#xff1a;向系统其他部分展现的硬件接口 内部结构&#xff1a;设备相关特定实现&#xff0c;几个芯片&#xff0c;CPU和通用内存等 3. 标准协议 While (STATUS BYSY); a、轮询设…
阅读更多...
第三节：提供者、消费者、Eureka

第三节：提供者、消费者、Eureka

一、 提供者 消费者&#xff08;就是个说法、定义&#xff0c;以防别人叭叭时听不懂&#xff09; 服务提供者&#xff1a;业务中被其他微服务调用的服务。&#xff08;提供接口给其他服务调用&#xff09;服务消费者&#xff1a;业务中调用其他微服务的服务。&#xff08;调用…
阅读更多...
Windows系统下Elasticsearch-7.15.2安装

Windows系统下Elasticsearch-7.15.2安装

一、环境 此次笔记使用的运行环境以及软件版本 系统:WIN10 JDK版本&#xff1a;1.8 Elasticsearch版本&#xff1a;7.15.2 elasticsearch-head版本&#xff1a;最新 IK分词器版本&#xff1a;7.15.2 Kibana版本&#xff1a;7.15.2 二、Elasticsearch基本知识 2.1 介绍…
阅读更多...
腾讯云优惠券领取入口及使用指南

腾讯云优惠券领取入口及使用指南

腾讯云作为国内领先的云计算服务商&#xff0c;提供了丰富的云产品和服务。为了帮助用户更好地享受腾讯云的服务&#xff0c;腾讯云推出了各种优惠券&#xff0c;包括新用户优惠、老用户优惠等。本文将为大家介绍腾讯云优惠券的领取入口和使用指南。 一、腾讯云优惠券领取入口 …
阅读更多...
Certum SSL证书

Certum SSL证书

为了确保在线交易的安全性&#xff0c;以及保护敏感信息免受网络威胁&#xff0c;使用SSL&#xff08;Secure Socket Layer&#xff09;证书成为了必要选择。其中&#xff0c;波兰认证机构Certum提供的SSL证书以其高度的安全性和可信赖性&#xff0c;得到了全球用户的广泛认可。…
阅读更多...
蓝桥杯物联网竞赛_STM32L071_6_RTC显示

蓝桥杯物联网竞赛_STM32L071_6_RTC显示

作用&#xff1a; RTC在STM32微控制器中通常由一个独立的低功耗晶振和相关的寄存器组成。它可以独立于主处理器运行&#xff0c;即使在系统电源关闭的情况下(需要备用纽扣电池)&#xff0c;也能继续计时和记录日期。注意&#xff1a;RTC是芯片内部的功能&#xff0c;并没有和G…
阅读更多...
网络运维与网络安全 学习笔记2023.12.2

网络运维与网络安全 学习笔记2023.12.2

网络运维与网络安全 学习笔记 第三十三天 今日目标 Linux系统综述、部署本地Linux、配置Linux网络 SSH远程控制、远程文档管理、选购ECS云主机 Linux系统综述 Linux是一种操作系统 Linux之父&#xff0c;Linus Torwalds 1991年10月&#xff0c;发布0.02版&#xff08;第一…
阅读更多...
OOM了？物理内存不够了？试试这个方法来提升内存容量，不花钱的

OOM了？物理内存不够了？试试这个方法来提升内存容量，不花钱的

通过增加虚拟内存来提高内存使用 本文解决的实际问题&#xff1a; 当我们物理内存小的时候&#xff0c;会出现OOM&#xff0c;然后服务自动死掉的情况。因为物理内存大小是固定的&#xff0c;有没有其他好的办法来解决呢&#xff1f;这里我们可以适当调整Linux的虚拟内存来协作…
阅读更多...
FreeRTOS第2天：

FreeRTOS第2天：

1. 二值信号量简介&#xff08;386.11&#xff09; 什么是信号量&#xff1f; 信号量&#xff08;Semaphore&#xff09;&#xff0c;是在多任务环境下使用的一种机制&#xff0c;是可以用来保证两个或多个关键代码段不被并 发调用。信号量这个名字&#xff0c;我们可以把它拆…
阅读更多...
Android BT HCI分析简介

Android BT HCI分析简介

对于蓝牙开发者来说&#xff0c;通过HCI log可以帮助我们更好地分析问题&#xff0c;理解蓝牙协议&#xff0c;就好像网络开发一定要会使用Wireshark分析网络协议一样。 本篇主要介绍HCI log的作用、如何抓取一份HCI log&#xff0c;并结合一个实际的例子来说明如何分析HCI log…
阅读更多...
eclipse中设置自动补齐代码

eclipse中设置自动补齐代码

eclipse中设置自动补齐代码 01 在window里找到preference 02 在preference里搜索content assist 03 在Java的content assist设置 设置为.abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 04 apply and close即可
阅读更多...
mysql在linux环境下安装（rpm）以及初始化后的登录配置

mysql在linux环境下安装（rpm）以及初始化后的登录配置

注&#xff1a;该安装步骤转载于CSDN,下方配置为原创 按照图片安装并初始化完成MySQL等操作后进行&#xff1b; 安装对于rpm包集合 1-查看安装情况&#xff08;有4个路径&#xff09; whereis mysql 2-查看服务状态 systemctl status mysql 3-初始化数据库 mysqld --initial…
阅读更多...
最新文章

Copyright @ 2022~2023