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

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

推荐阅读

string
深入理解KMP算法中的next数组：北大OJ 2406题解

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

蜡笔小新 2024-12-28 11:30:01
string
USACO 2014 Jan - Moolympics区间记录优化算法

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

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

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

蜡笔小新 2024-12-27 11:26:39
string
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

蜡笔小新 2024-12-26 20:04:36
string
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
string
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16
string
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
string
java编写的简易计算器

主要用了2个类来实现的，话不多说，直接看运行结果，然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]

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

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

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

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

蜡笔小新 2024-12-26 18:47:12
string
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
sum
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
char
文件描述符、文件句柄与打开文件之间的关联解析

本文详细探讨了文件描述符、文件句柄和打开文件之间的关系，通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]

蜡笔小新 2024-12-26 14:00:46
char
C语言链表动态创建：头插法与尾插法详解

本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法，包括具体的实现代码和运行示例。通过这些内容，读者可以更好地理解和掌握链表的基本操作。 ... [详细]

蜡笔小新 2024-12-26 13:59:07
merge
计算机图形学实训：OpenGL入门与直线光栅化算法

本教程涵盖OpenGL基础操作及直线光栅化技术，包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践，帮助读者掌握OpenGL的基本使用方法。 ... [详细]

蜡笔小新 2024-12-26 12:24:25

裸身耍丶暧昧800

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

Tags | 热门标签

RankList | 热门文章