广度优先搜索学习五例之二（JAVA）

128kj

再次强调：
图的广度优先搜索，要遵守以下规则：
(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[0];              temp2.y = temp1.y + dir[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[0];  //在同一方向上继续走                temp2.y += dir[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[j]=line.charAt(j-1);  //地图        }             nPacase = 0;                        //外围加框           for(int i=0; i<=w+1; i++)          {              g[0] = ' ';              g[h+1] = ' ';          }          for(int i=0; i<=h+1; ++i)          {              g[0] = ' ';              g[w+1] = ' ';          }          //测试图的正确性          /* for(int i=0; i<=h+1; i++)         {             for(int j=0; j<=w+1; j++)                 System.out.print(g[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[j]=g[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();      }    }   }  
下载源码：