迷宫问题的DFS

2024-08-21 16:18
文章标签 问题 dfs 迷宫

本文主要是介绍迷宫问题的DFS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题我还是觉得bfs简单,可是这货居然DFS也能解,Orz之余,学习学习......

文章转自 http://www.2cto.com/kf/201308/235681.html

POJ 3984 迷宫问题 (DFS(深度优先搜索))

迷宫问题
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6322   Accepted: 3673

Description

定义一个二维数组:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input

一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output

左上角到右下角的最短路径,格式如样例所示。
Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路: DFS算法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.*;
import java.util.*;
public class Main {
public static int map[][] = new int [5][5];
public static int fx[] = { 0, 0, 1, -1 };
public static int fy[] = { 1, -1, 0, 0 };
public static int px, py;
public static void main(String[] args) {
Scanner sc = new Scanner( new BufferedInputStream(System.in));
while (sc.hasNextInt()) {
for ( int i = 0; i < map.length; i++) {
for ( int j = 0; j < map[i].length; j++) {
map[i][j] = sc.nextInt();
}
}
map[0][0] = 3; //标记走过
px = 0;
py = 0;
DFS(0, 0); 
}
}
public static void DFS( int p1, int p2) {
if (p1 == map.length - 1 && p2 == map[0].length - 1){
out();
return ;
}
else {
//四个方向进行判定
for ( int i = 0; i < 4; i++) {
int px = p1 + fx[i];
int py = p2 + fy[i];
if (check(px, py)) {
map[px][py] = 3; //标记走过的路
DFS(px, py);
}
}
}
}
public static void out() {
for ( int i = 0; i <5; i++) {
for ( int j = 0; j <5; j++) {
if (map[i][j] == 3) {
System.out.println( "(" + i + ", " + j + ")" );
}
}
}
}
public static boolean check( int p1, int p2) {
if (p1 < 0 || p1 > map[0].length - 1 || p2 < 0 || p2 > map.length - 1
|| map[p1][p2] != 0)
return false ;
else
return true ;
}
}

这篇关于迷宫问题的DFS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1093660

相关文章

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socket read timed out的问题

《如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socketreadtimedout的问题》:本文主要介绍解决Druid线程... 目录异常信息触发场景找到版本发布更新的说明从版本更新信息可以看到该默认逻辑已经去除总结异常信息触发场景复