- 浏览: 601289 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
先继续“深度优先搜索学习五例之三”http://128kj.iteye.com/admin/blogs/1702286中的迷宫,那里用栈实现了深搜,但只输出了一条路径,下面程序用递归实现深搜,输出所有到出口的路径和数目:
运行结果:
.........................................省略很多
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001222
01111102
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001220
01111122
.......................
共有72条路径
再看下面POJ1562:
题意:在一个n*m的地图上探索有多少块油田,'@'表示单位油田,相邻的(上下左右与对角线)单位油田为一个大油田,问有多少个大油田。
Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2
就是求多少个连通分量,顺序扫描,每扫面到一个@,并且这个格子没有被深度遍历过,就进行一次深度优先遍历.
下载:
import java.util.Stack; //////////////////////////////////////////////// //深度优先搜索之迷宫问题:输出所有到出口的路径 public class MazeDsf{ private static final int M=9; private static final int N=8; private int total; //迷宫矩阵,0为通道,1为障碍 //入口(0,0),出口(8,7) private int[][] Matrix = { { 0, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1, 0 }, { 0, 1, 0, 0, 0, 0, 1, 0 }, { 0, 1, 0, 1, 1, 0, 1, 0 }, { 0, 1, 0, 0, 0, 0, 1, 1 }, { 0, 1, 0, 0, 1, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 0, 0 } }; public MazeDsf(){ total=0; } //右下上左 private int x_off[] = {0,1,-1,0}; private int y_off[] = {1,0,0,-1}; //输出迷宫 private void PrintMatrix(){ System.out.println("入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:"); for(int i = 0; i < M; ++i){ for(int j = 0; j < N; ++j) System.out.print(Matrix[i][j]); System.out.println(); } } //深度优先搜索所有可能的路径 public void dfs(int x,int y) { Matrix[x][y]=2; if(x == 8&& y == 7){ //输出找到的路径 total++; PrintMatrix(); } for(int i = 0; i<4; ++i){ //右下上左 int nx = x + x_off[i]; int ny = y + y_off[i]; if(nx >= 0 && nx < M && ny>=0 && ny< N && Matrix[nx][ny] == 0){ dfs(nx,ny); } } Matrix[x][y] =0;//这里就是回溯,很重要!!! } public int getTotal(){ return total; } //测试代码主函数 public static void main(String args[]) { MazeDsf maze=new MazeDsf(); maze.PrintMatrix(); maze.dfs(0,0); System.out.print("共有"+maze.getTotal()+"条路径"); } }
运行结果:
.........................................省略很多
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001222
01111102
入口(0,0),出口(8,7)的迷宫,2为通道,1为障碍:
21111111
20000000
21111010
22202210
01222210
01011210
01000211
01001220
01111122
.......................
共有72条路径
再看下面POJ1562:
题意:在一个n*m的地图上探索有多少块油田,'@'表示单位油田,相邻的(上下左右与对角线)单位油田为一个大油田,问有多少个大油田。
Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2
就是求多少个连通分量,顺序扫描,每扫面到一个@,并且这个格子没有被深度遍历过,就进行一次深度优先遍历.
import java.util.Scanner; public class Main{ int m, n; char map[][]; int move[][] = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} }; public Main(int m,int n,char[][] map){ this.m=m; this.n=n; this.map=map; } private void DFS(int si, int sj) { for (int i = 0; i<8; ++i) { int mi = si + move[i][0]; int mj = sj + move[i][1]; if (mi >= m|| mj >= n || mi < 0 ||mj < 0) continue ; if (map[mi][mj] == '@') { map[mi][mj] = '*'; DFS(mi, mj); } } return ; } public static void main(String args[]){ Scanner in=new Scanner(System.in); while(true){ int a=in.nextInt(); int b=in.nextInt(); if(a==0&&b==0)break; int count=0; char[][] map=new char[a][b]; for(int i=0;i<a;i++){ String s=in.next(); for(int j=0;j<b;j++) map[i][j]=s.charAt(j); } Main m=new Main(a,b,map); int answer=0; for (int i = 0; i<a; i++) for (int j = 0; j<b; j++) if (map[i][j] == '@') { map[i][j] = '*'; m.DFS(i, j); ++answer; } System.out.printf("%d\n", answer); } } }
下载:
- Main1562.zip (1.6 KB)
- 下载次数: 0
发表评论
-
龙抬头
2014-11-10 15:06 621... -
求推箱子的最小步数(java)
2014-05-06 08:32 3746题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3054POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3314回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1837一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1924很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5927Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4045一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1243一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2311一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2265继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4959深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1442如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1153例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1492广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1672有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2123再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2272凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1110最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1268矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
深度优先搜索(DFS, Depth-First Search)是一种用于遍历或搜索树或图的算法,它从根节点开始,沿着某一条路径一直深入到叶子节点,然后再回溯寻找其他路径。在本例中,我们有两个Java文件:MazeDsf.java 和 Queen....
在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...
这篇博文“深度优先搜索学习五例之五(JAVA)”可能介绍了DFS在解决实际问题中的应用,尽管描述中没有给出具体细节,但我们可以从一般的角度来探讨DFS以及其在Java中的实现。 DFS的基本思想是从根节点开始,沿着某...
通常,这样的教程会包括代码实现、步骤解析以及为什么选择BFS而不是深度优先搜索(Depth-First Search, DFS)的原因。 【标签】:“源码”、“工具” “源码”标签表明文章会包含实际的Java代码示例,读者可以参考...
2. Main1.java:这个文件可能是对BFS的另一种实现,或者是辅助Main.java进行特定任务的类,比如提供额外的测试用例,或者实现了与BFS相关的其他算法(如深度优先搜索DFS)进行对比。 综上所述,这个压缩包文件的...
在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...
- **深度优先搜索(DFS)**:递归地探索节点的邻接节点,用于遍历或搜索图。 - **广度优先搜索(BFS)**:使用队列数据结构,按照距离从起点到终点的顺序访问节点。 4. **动态规划(DP)**: - **斐波那契数列**:使用...
2. **搜索算法**:如线性搜索、二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些是解决查找问题的基础,对于理解数据结构至关重要。 3. **图论算法**:例如Dijkstra最短路径算法、Floyd-Warshall所有对...
2. **搜索算法**:二分查找、深度优先搜索、广度优先搜索等,探讨如何在数据结构中高效地查找目标元素。 3. **数据结构**:栈、队列、链表、树、图等,如何利用它们来实现各种算法。 4. **动态规划**:如斐波那契...
9. **DFS(深度优先搜索)算法**:DFS是一种用于遍历或搜索树或图的算法,沿着树的深度遍历树的节点,尽可能深地搜索树的分支。在Java中,DFS可以借助于递归或栈来实现。 这些知识点涵盖了计算机科学基础和算法设计...
2. **搜索算法**:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS),这些算法在处理数据集合时非常实用。 3. **图论算法**:Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法,它们在网络...
这个类可能实现了A*算法、Dijkstra算法或者深度优先搜索(DFS)等常见的寻找最短路径的算法。这些算法的核心目标是找到从起点到终点的最短路径,同时尽量避免无效的探索。 以A*算法为例,它结合了Dijkstra算法的...
深度遍历(又称深度优先遍历)是指沿着树的深度遍历树的节点,尽可能深地搜索树的分支,当节点v的所有出边都已被探寻过,搜索将回溯到发现节点v的那条边的起始节点。在目录结构中,这意味着如果当前遍历到的文件是...
在实现这个项目时,我们可能需要学习图算法,如深度优先搜索(DFS)或广度优先搜索(BFS),用于寻找从起点到终点的最短路径。数据结构如栈或队列会在这里发挥重要作用。同时,我们需要理解如何将迷宫表示为二维数组...
2. **搜索算法**:二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些算法在处理数据查找和遍历树形结构时非常有效。 3. **图论算法**:最短路径问题(Dijkstra算法、Floyd算法),最小生成树(Prim算法...
这些代码可能包括简单的排序算法(冒泡、选择、插入、快速、归并等)、查找算法(顺序、二分、哈希等)、图算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)以及其他复杂的数据结构实现。 5. **学习...
2. **搜索算法**:如二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)。这些算法在处理大量数据时具有重要作用,如在树和图结构中寻找特定元素或路径。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-...
3. **图论算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等。 4. **动态规划**:解决许多复杂问题的有效方法,如背包问题、最长公共子序列、...
这可能需要使用图遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)。 3. **文件输入与输出**: - 输入通常包含每个建筑物的长、宽、高和位置信息,可能以CSV、JSON或其他格式存储。Java的`Scanner`类可用于...