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

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

阅读更多
再次强调:
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点),标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。



【题(poj 1101)】:给出一个地图,标有X的地方不能经过,给出一对坐标(2,3),(5,3),问这对坐标能否相连通(连连看),如果能则输出最少要经过的路段(路段是指一段直线,如果中途发生转折则就是两个路段);如果不能则输出impossible。


【注意】:
(1)本题的路可以在在给定的地图外走,如:W=5,H=4,则可选的路范围为0<=w<=W+1,0<=h<=H+1;
另外注意每一组测试数据在输出结果后要输出一行空行
(2)只有一个注意点该题搜的不是最短路径,而是最少拐弯次数(类似于连连看),再者要处理好地图与坐标的关系。

Sample Input


Sample Output

Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.

代码:
import java.util.*;
  class Piece{ //顶点类
    int x, y;  
    int step;  //路段数

    public Piece(){
        this(0,0,0);
    }

    public Piece(int x,int y,int step){
      this.x=x;
      this.y=y;
      this.step=step;
    }
  }

public class Main{
   private char g[][];  //地图
   private int w, h;  //地图的宽和高
   private int dir[][] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  //四个方向,任意一点可能有四个邻接点(相通才是)
   private boolean visited[][];  

   private Piece start, goal;  //起点和目标点

   public Main(int w,int h, Piece start, Piece goal,char[][] g){
         this.w=w;
         this.h=h;
         this.g=g;
         this.start=start;
         this.goal=goal;
         visited=new boolean[h+2][w+2];
   }

   public Piece getGoal(){
     return goal;
   }

   /* BFS访问与start最近的、相通(邻接)点并标记,路段数是1的是同一层,第一层完了再搜索第二层
     路段数是2的是第二层,。。。(就一个四叉树而已)标记过的点不必再标记。*/
   public void bfs(){  
    int i;  
   	Queue<Piece> que = new LinkedList<Piece>();
	que.add(start);  //起点入队
        visited[start.x][start.y] = true;  //标记为已访问
    while(!que.isEmpty())  //队列非空
    {  
        Piece temp1 = que.poll();  //出队
        if(temp1.x==goal.x && temp1.y==goal.y && goal.step>temp1.step)  
        {  
                goal.step = temp1.step;  
                break;//如果搜索到了目标,程序退出。
         }  

        //访问temp1的四个邻接点,左、右、下、上
        for(i=0; i<4; ++i)  
        {  
           
            Piece temp2=new Piece();  
            temp2.x = temp1.x + dir[i][0];  
            temp2.y = temp1.y + dir[i][1];  
           while(temp2.x>=0 && temp2.x<=h+1    
                && temp2.y>=0 && temp2.y<=w+1 && !visited[temp2.x][temp2.y] &&g[temp2.x][temp2.y]==' '){   //temp2与temp1相通
               
                visited[temp2.x][temp2.y] = true;  //标记为已访问
                temp2.step = temp1.step+1;  //同一方向上相通的点,路段数相同。
                que.add(new Piece(temp2.x,temp2.y,temp2.step));  //入队
                 
                temp2.x += dir[i][0];  //在同一方向上继续走
                temp2.y += dir[i][1];  
               
            }     
        }  
    }  
}  

public static void main(String args[]){  
    Scanner in=new Scanner(System.in);
    
    int nPacase=0;
    int nCase=0;
    Piece start=new Piece();//起点
    Piece goal=new Piece();//目标点
    while(true)   {  

     int w=in.nextInt();
     int h=in.nextInt();
      in.nextLine();
     if(w==0&&h==0) break;
     char g[][]=new char[h+2][w+2];
     for(int i=1; i<=h; ++i)  
        {  
            String line=in.nextLine();
              for(int j=1; j<=w; j++)  
                g[i][j]=line.charAt(j-1);  //地图
        }  
   
        nPacase = 0;  
              
        //外围加框   
        for(int i=0; i<=w+1; i++)  
        {  
            g[0][i] = ' ';  
            g[h+1][i] = ' ';  
        }  
        for(int i=0; i<=h+1; ++i)  
        {  
            g[i][0] = ' ';  
            g[i][w+1] = ' ';  
        }  

        //测试图的正确性   
       /* for(int i=0; i<=h+1; i++) 
        { 
            for(int j=0; j<=w+1; j++) 
                System.out.print(g[i][j]); 
              System.out.println(); 
        }  */

        
        System.out.println("Board #"+(++nCase)+":");  
        while(1==1)  
        {  
             char[][] c=new char[h+2][w+2];
              
          for(int i=0; i<=h+1; i++) 
           { 
            for(int j=0; j<=w+1; j++) 
                c[i][j]=g[i][j]; //克隆数组
             
           }  
    
            start.y=in.nextInt();
            start.x=in.nextInt();
            goal.y=in.nextInt();
            goal.x=in.nextInt();
         
            start.step = 0;  
            goal.step = Integer.MAX_VALUE;  
            if(start.x==0 && start.y==0 && goal.x==0 && goal.y==0)  //程序退出
                break;  
          
            if(c[goal.x][goal.y] == 'X')  
            {  
                c[goal.x][goal.y] = ' ';  
            
            }  
            Main m=new Main(w,h,start,goal,c);
            m.bfs();  
            
            if(m.getGoal().step == Integer.MAX_VALUE)  
                System.out.println("Pair "+(++nPacase)+": impossible.");  
            else  
                System.out.println("Pair "+(++nPacase)+": "+m.getGoal().step+" segments.");  


            }  
        System.out.println();
      }  
  }
   
}  

下载源码:
  • 大小: 6.5 KB
  • 大小: 5.4 KB
分享到:
评论

相关推荐

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

    【标题】:“广度优先搜索学习五例之四” 在计算机科学中,广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历或搜索树或图的算法。它按照从根节点开始,逐层进行探索的方式进行。在本案例中,我们可能...

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

    **广度优先搜索(Breadth-First Search, BFS)**是一种在图或树中进行搜索的算法,常用于寻找最短路径或者遍历结构。它遵循“先探索节点的所有邻居,再探索邻居的邻居”的策略,从起点开始,逐层向外扩展。BFS的关键...

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

    【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...

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

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

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

    由于DFS具有深度优先的特点,它往往能在较深的分支找到解决方案,但可能会错过较浅的解,因此在某些情况下,如广度优先搜索(BFS)可能会是更好的选择。 总结来说,"深度优先搜索学习五例之四(JAVA)"的主题涵盖了...

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

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

    Java趣味编程100例源代码

    例如,可能需要设计一个栈来实现后缀表达式的计算,或者利用队列进行广度优先搜索。通过实践,读者可以加深对数据结构的理解,提高代码的可读性和性能。 接着,算法是编程的灵魂。本书的编程题目中很可能包含排序...

    JAVA算法100例,全源码.zip

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

    JAVA算法100例

    - **广度优先搜索(BFS)**:使用队列数据结构,按照距离从起点到终点的顺序访问节点。 4. **动态规划(DP)**: - **斐波那契数列**:使用记忆化或自底向上的方法求解,避免重复计算。 - **背包问题**:如0-1背包...

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

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

    java经典算法40例+答案

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

    java2课程设计源代码大全

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

    JAVA经典算法42例

    此外,文档中的其他实例可能包括搜索算法(如二分查找、广度优先搜索等)、图论算法(如Dijkstra最短路径、Floyd-Warshall算法等)以及动态规划、贪心算法等。学习这些算法不仅可以提升编程能力,还能培养解决问题的...

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

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

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

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

    轮廓问题的java实现

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

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

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

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

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

    java象棋对战

    判断棋局胜负可能需要深度优先搜索(DFS)或广度优先搜索(BFS);而象棋的AI对战则可能涉及最小-最大搜索算法配合Alpha-Beta剪枝。 4. **状态管理**:棋盘上的每一步操作都会改变游戏的状态,这需要一个高效的数据...

Global site tag (gtag.js) - Google Analytics