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

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

推荐阅读

input
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
include
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
include
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
input
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
include
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
input
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
int
Java太阳系小游戏分析和源码详解

本文介绍了一个基于Java的太阳系小游戏的分析和源码详解。通过对面向对象的知识的学习和实践，作者实现了太阳系各行星绕太阳转的效果。文章详细介绍了游戏的设计思路和源码结构，包括工具类、常量、图片加载、面板等。通过这个小游戏的制作，读者可以巩固和应用所学的知识，如类的继承、方法的重载与重写、多态和封装等。 ... [详细]

蜡笔小新 2023-12-14 19:53:34
object
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
format
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
int
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
object
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
include
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
object
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
int
电话号码的字母组合解题思路和代码示例

本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]

蜡笔小新 2023-12-14 18:50:22
int
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21

裸身耍丶暧昧800

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

Tags | 热门标签

RankList | 热门文章