`
128kj
  • 浏览: 601289 次
  • 来自: ...
社区版块
存档分类
最新评论

深度优先搜索学习五例之四(JAVA)

阅读更多
   先继续“深度优先搜索学习五例之三”http://128kj.iteye.com/admin/blogs/1702286中的迷宫,那里用栈实现了深搜,但只输出了一条路径,下面程序用递归实现深搜,输出所有到出口的路径和数目:
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);  
    }  
}
}  


下载:

分享到:
评论

相关推荐

    深度优先搜索学习五例之三(JAVA)

    深度优先搜索(DFS, Depth-First Search)是一种用于遍历或搜索树或图的算法,它从根节点开始,沿着某一条路径一直深入到叶子节点,然后再回溯寻找其他路径。在本例中,我们有两个Java文件:MazeDsf.java 和 Queen....

    深度优先搜索学习五例之一(JAVA)

    在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...

    深度优先搜索学习五例之五(JAVA)

    这篇博文“深度优先搜索学习五例之五(JAVA)”可能介绍了DFS在解决实际问题中的应用,尽管描述中没有给出具体细节,但我们可以从一般的角度来探讨DFS以及其在Java中的实现。 DFS的基本思想是从根节点开始,沿着某...

    广度优先搜索学习五例之二(JAVA)

    通常,这样的教程会包括代码实现、步骤解析以及为什么选择BFS而不是深度优先搜索(Depth-First Search, DFS)的原因。 【标签】:“源码”、“工具” “源码”标签表明文章会包含实际的Java代码示例,读者可以参考...

    广度优先搜索学习五例之三

    2. Main1.java:这个文件可能是对BFS的另一种实现,或者是辅助Main.java进行特定任务的类,比如提供额外的测试用例,或者实现了与BFS相关的其他算法(如深度优先搜索DFS)进行对比。 综上所述,这个压缩包文件的...

    广度优先搜索学习五例之五

    在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...

    JAVA算法100例

    - **深度优先搜索(DFS)**:递归地探索节点的邻接节点,用于遍历或搜索图。 - **广度优先搜索(BFS)**:使用队列数据结构,按照距离从起点到终点的顺序访问节点。 4. **动态规划(DP)**: - **斐波那契数列**:使用...

    JAVA算法100例,全源码.zip

    2. **搜索算法**:如线性搜索、二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些是解决查找问题的基础,对于理解数据结构至关重要。 3. **图论算法**:例如Dijkstra最短路径算法、Floyd-Warshall所有对...

    [java软件技术文档doc]java经典算法40例

    2. **搜索算法**:二分查找、深度优先搜索、广度优先搜索等,探讨如何在数据结构中高效地查找目标元素。 3. **数据结构**:栈、队列、链表、树、图等,如何利用它们来实现各种算法。 4. **动态规划**:如斐波那契...

    华为机考100例java.rar

    9. **DFS(深度优先搜索)算法**:DFS是一种用于遍历或搜索树或图的算法,沿着树的深度遍历树的节点,尽可能深地搜索树的分支。在Java中,DFS可以借助于递归或栈来实现。 这些知识点涵盖了计算机科学基础和算法设计...

    java经典算法40例+答案

    2. **搜索算法**:二分查找、线性查找、深度优先搜索(DFS)和广度优先搜索(BFS),这些算法在处理数据集合时非常实用。 3. **图论算法**:Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法,它们在网络...

    java实现的求迷宫最短路径算法

    这个类可能实现了A*算法、Dijkstra算法或者深度优先搜索(DFS)等常见的寻找最短路径的算法。这些算法的核心目标是找到从起点到终点的最短路径,同时尽量避免无效的探索。 以A*算法为例,它结合了Dijkstra算法的...

    java 对文件夹目录进行深度遍历实例代码

    深度遍历(又称深度优先遍历)是指沿着树的深度遍历树的节点,尽可能深地搜索树的分支,当节点v的所有出边都已被探寻过,搜索将回溯到发现节点v的那条边的起始节点。在目录结构中,这意味着如果当前遍历到的文件是...

    java2课程设计源代码大全

    在实现这个项目时,我们可能需要学习图算法,如深度优先搜索(DFS)或广度优先搜索(BFS),用于寻找从起点到终点的最短路径。数据结构如栈或队列会在这里发挥重要作用。同时,我们需要理解如何将迷宫表示为二维数组...

    [电子书][Java类]JAVA经典算法42例

    2. **搜索算法**:二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)等,这些算法在处理数据查找和遍历树形结构时非常有效。 3. **图论算法**:最短路径问题(Dijkstra算法、Floyd算法),最小生成树(Prim算法...

    数据结构与算法分析Java语言描述第三版书中例题源代码(Mark·Allen·Weiss著)

    这些代码可能包括简单的排序算法(冒泡、选择、插入、快速、归并等)、查找算法(顺序、二分、哈希等)、图算法(深度优先搜索、广度优先搜索、最小生成树、最短路径等)以及其他复杂的数据结构实现。 5. **学习...

    JAVA经典算法收集整理 以及Java算法大全(近100种算法打包).rar

    2. **搜索算法**:如二分查找、深度优先搜索(DFS)、广度优先搜索(BFS)。这些算法在处理大量数据时具有重要作用,如在树和图结构中寻找特定元素或路径。 3. **图论算法**:如Dijkstra最短路径算法、Floyd-...

    Java经典算法(包你们划算)

    3. **图论算法**:如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法等。 4. **动态规划**:解决许多复杂问题的有效方法,如背包问题、最长公共子序列、...

    轮廓问题的java实现

    这可能需要使用图遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)。 3. **文件输入与输出**: - 输入通常包含每个建筑物的长、宽、高和位置信息,可能以CSV、JSON或其他格式存储。Java的`Scanner`类可用于...

Global site tag (gtag.js) - Google Analytics