当前位置: 开发笔记 > 编程语言 > 正文

POJ2248AKnight'sJourney(DFS)

作者：裸身耍丶暧昧800 | 来源：互联网 | 2023-10-13 11:56

题目链接。题目大意：给定一个矩阵，马的初始位置在（0,0），要求给出一个方案，使马走遍所有的点。

题目链接。

题目大意&＃xff1a;

给定一个矩阵&＃xff0c;马的初始位置在&＃xff08;0,0&＃xff09;&＃xff0c;要求给出一个方案&＃xff0c;使马走遍所有的点。

列为数字&＃xff0c;行为字母&＃xff0c;搜索按字典序。

分析&＃xff1a;

用 vis[x][y] 标记是否已经访问。因为要搜索所有的可能&＃xff0c;所以没搜索完一次要把vis[x][y]标记为未访问。详情见代码。

用 p[x][y] 表示 (x,y)点的祖先&＃xff0c;以便输出路径。

dfs搜索即可。

#include
#include
#include <string>
#include
#include using namespace std;const int maxn &＃61; 30;
const int VAL &＃61; 10000;int dx[] &＃61; {-1, 1, -2, 2, -2, 2, -1, 1}; //搜索顺序是字典序
int dy[] &＃61; {-2, -2, -1, -1, 1, 1, 2, 2};bool vis[maxn][maxn];
int p[maxn][maxn], ex, ey;
int cnt, total, n, m;bool dfs(int x, int y, int px, int py) {p[x][y] &＃61; px*VAL&＃43;py;cnt&＃43;&＃43;;//如果已经走遍的点等于总点数&＃xff0c;表示已经全部访问完if(cnt &＃61;&＃61; total) {ex &＃61; x; ey &＃61; y;return true;}for(int d&＃61;0; d<8; d&＃43;&＃43;) {int nx &＃61; x&＃43;dx[d];int ny &＃61; y&＃43;dy[d];if(nx <0 || ny <0 || nx >&＃61; n || ny >&＃61; m) continue;if(vis[nx][ny]) continue;vis[nx][ny] &＃61; true; //标记已访问if(dfs(nx, ny, x, y)) return true;vis[nx][ny] &＃61; false; //标记未访问cnt--; //已访问的数要减一
}return false;
}void print(int x, int y) {if(x &＃61;&＃61; 0 && y &＃61;&＃61; 0) return;int e &＃61; p[x][y];int px &＃61; e/VAL, py &＃61; e%VAL;print(px, py);printf("%c%d", y&＃43;&＃39;A&＃39;, x&＃43;1); //y对应字母&＃xff0c;x对应数字
}int main(){int T;scanf("%d", &T);for(int kase&＃61;1; kase<&＃61;T; kase&＃43;&＃43;) {scanf("%d%d", &n, &m);cnt &＃61; 0; total &＃61; n*m;memset(vis, 0, sizeof(vis));vis[0][0] &＃61; true;printf("Scenario #%d:\n", kase);if(dfs(0, 0, 0, 0)) { //有方案&＃xff0c;输出printf("A1");print(ex, ey);putchar(&＃39;\n&＃39;);}else printf("impossible\n");putchar(&＃39;\n&＃39;);}return 0;
}

转:https://www.cnblogs.com/tanhehe/p/3223506.html

推荐阅读

case
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
case
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
object
Java 中的 BigDecimal pow()方法，示例

Java 中的 BigDecimal pow()方法，示例 ... [详细]

蜡笔小新 2024-12-27 20:54:03
const
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
case
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
python
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
buffer
golang常用库：配置文件解析库/管理工具viper使用

golang常用库：配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库，是由大神SteveFrancia开发，他在google领导着golang的 ... [详细]

蜡笔小新 2024-12-28 13:47:52
buffer
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
buffer
Java 中 Writer flush()方法，示例

Java 中 Writer flush()方法，示例 ... [详细]

蜡笔小新 2024-12-28 06:41:52
request
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
random
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
request
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新 2024-12-27 16:07:12
process
XNA 3.0 游戏编程：从 XML 文件加载数据

本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件，并通过内容管道加载到游戏中。此外，还会涉及自定义类型读取器和写入器的实现。 ... [详细]

蜡笔小新 2024-12-27 11:39:44
jsp
使用 NSTimer 实现倒计时功能

本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]

蜡笔小新 2024-12-26 19:08:19
bit
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12

裸身耍丶暧昧800

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章