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;
}

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

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

相关文章

《QT实用小工具·九》设备按钮控件

1、概述 源码放在文章末尾 该项目实现了设备按钮控件&#xff0c;主要包含如下功能&#xff1a; 可设置按钮样式 圆形、警察、气泡、气泡2、消息、消息2。可设置按钮颜色 布防、撤防、报警、旁路、故障。可设置报警切换及对应报警切换的颜色。可设置显示的防区号。可设置是否…

实验报告答案

基本任务&#xff08;必做&#xff09; 先用普通用户&#xff08;自己的姓名拼音&#xff09;登录再操作 编程有代码截图和执行过程结果截图 代写获取&#xff1a; https://laowangall.oss-cn-beijing.aliyuncs.com/studentall.pdf 1. Linux的Shell编程 &#xff08;1&am…

实操:Dropzone.js实现文件上传

&#x1f3e0;官网 点我前往 &#x1f953;依赖 <script src"https://unpkg.com/dropzone5/dist/min/dropzone.min.js"></script> <link rel"stylesheet" href"https://unpkg.com/dropzone5/dist/min/dropzone.min.css" type&…

unity工程输出的log在哪里?

在编辑器里进行活动输出的log位置&#xff1a; C:\Users\username\AppData\Local\Unity\Editor\Editor.log ------------------------------------ 已经打包完成&#xff0c;形成的exe运行后的log位置&#xff1a; C:\Users\xxx用户\AppData\LocalLow\xx公司\xx项目

【Qt】事件

目录 一、介绍 二、进入离开事件 三、鼠标事件 3.1 鼠标单击事件 3.2 鼠标释放事件 3.3 鼠标双击事件 3.4 鼠标移动事件 3.5 滚轮事件 四、按键事件 4.1 单个按键 4.2 组合按键 五、定时器 5.1 QTimerEvent类 5.2 QTimer类 5.3 获取系统日期及时间 六、事件分…

【游戏逆向】逆向基础----CE使用和基础

windows逆向中&#xff0c;CE扮演着不可或缺的角色。 其根本原因是&#xff0c;上手简单,功能强大&#xff0c;提供多方位的突破口。 点击小电脑图标&#xff0c; 选择我们想要调试的程序&#xff0c; 就可以附加调试了。 很多的游戏保护驱动以及反调试手段&#xff0c;都针对…

澳门媒体发稿套餐9个增长技巧解析-华媒舍

澳门作为一个国际知名的旅游胜地&#xff0c;拥有丰富的媒体资源。利用澳门媒体发稿&#xff0c;既可以提升品牌知名度&#xff0c;又可以吸引更多的目标受众。下面是9个利用澳门媒体发稿套餐的增长技巧&#xff0c;帮助你充分发挥媒体的作用&#xff0c;实现品牌的增长。 1. 制…

机器学习的模型校准

背景知识 之前一直没了解过模型校准是什么东西&#xff0c;最近上班业务需要看了一下&#xff1a; 模型校准是指对分类模型进行修正以提高其概率预测的准确性。在分类模型中&#xff0c;预测结果通常以类别标签形式呈现&#xff08;例如&#xff0c;0或1&#xff09;&#xf…

注意力机制篇 | YOLOv8改进之添加LSKAttention大核卷积注意力机制 | 即插即用,实现有效涨点

前言:Hello大家好,我是小哥谈。LSKAttention是一种注意力机制,它在自然语言处理领域中被广泛应用。LSKAttention是基于Transformer模型中的Self-Attention机制进行改进的一种变体。在传统的Self-Attention中,每个输入序列中的元素都会与其他元素进行交互,以获取全局的上下…

Linux 命令 top 详解

1 top命令介绍 Linux系统中&#xff0c;Top命令主要用于实时运行系统的监控&#xff0c;包括Linux内核管理的进程或者线程的资源占用情况。这个命令对所有正在运行的进程和系统负荷提供不断更新的概览信息&#xff0c;包括系统负载、CPU利用分布情况、内存使用、每个进程的内容…

开源量化交易研究框架Hikyuu

Hikyuu Quant Framework 是一款基于 C/Python 的开源量化交易研究框架&#xff0c;用于策略分析及回测。其核心思想基于当前成熟的系统化交易方法&#xff0c;将整个系统化交易抽象为由市场环境判断策略、系统有效条件、信号指示器、止损 / 止盈策略、资金管理策略、盈利目标策…

分享three.js实现粒子背景

three.js中粒子效果的实现方式大概分为三种&#xff1a; 1、Javascript直接计算粒子的状态变化&#xff0c;即基于CPU实现&#xff1b; 2、Javascript通知顶点着色器粒子的生命周期&#xff0c;由顶点着色器运行&#xff0c;即基于GPU实现&#xff1b; 3、粒子生成与状态维护全…

QT实现NTP功能

一.NTP基础 1.NTP定义 NTP&#xff08;Network Time Protocol&#xff0c;网络时间协议&#xff09;是由RFC 1305定义的时间同步协议&#xff0c;用于分布式设备&#xff08;比如电脑、手机、智能手表等&#xff09;进行时间同步&#xff0c;避免人工校时的繁琐和由此引入的误…

【漏洞复现】极简云 download.php 接口处存在任意文件读取漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

什么是线程安全、怎么保证线程安全

目录 什么是线程安全 多线程编程中的三个核心概念 JMM内存模型 JMM内存模型怎么实现原子性、可见性 怎么保证线程安全 什么是线程安全 当多个线程访问一个对象时&#xff0c;如果不用考虑这些线程在运行时环境下的调度和交替执行&#xff0c;也不需要进行额外的同步&#x…

Rust---复合数据类型之结构体

目录 结构体的使用输出结果 结构体简化创建结构体更新语法元组结构体单元结构体&#xff08;unit struct&#xff09;结构体中的引用使用#[derive(Debug)]再次介绍 代码综合展示 与元组不同的是&#xff0c;结构体可以为内部的每个字段起一个富有含义的名称&#xff0c;因此无需…

基于SpringBoot+Vue的汽车租赁管理系统的设计和实现【附源码】

1、系统演示视频&#xff08;演示视频&#xff09; 2、需要交流和学习请联系

vivado适用于 UltraScale 和 UltraScale+ 器件的 eFUSE 寄存器访问和编程

FUSE_DNA &#xff1a; 唯一的器件 DNA 每个 UltraScale 器件都有唯一的器件 ID &#xff0c; 称为器件 DNA &#xff0c; 且赛灵思已将此 DNA 编程到器件中。用户无法对 FUSE_DNA 进行编程。 UltraScale 器件具有 96 位 DNA 。您可在 Vivado Design Suite Tcl 控制台中…

Matlab梁单元有限元编程:铁木辛柯梁VS欧拉梁

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…

openplc Linux 地址映射io,读写驱动数据等使用记录

1. 上一篇记录 openplc使用C语言文件读写驱动实现基本流程。 openPLC_Editor C语言编程 在mp157 arm板上调用io等使用记录_openplc c 编程-CSDN博客 2. 下面通过映射地址的方式控制io和读写驱动数据。 在runtime 环境的 hardware 硬件配置中 选择 python on Linux(PSM)&#…