广度优先搜索学习五例之二（JAVA）
再次强调：图的广度优先搜索，要遵守以下规则：
(0) 选取某一顶点作为开始搜索的起点（当前顶点），标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点，这个点必须是当前顶点的邻接点，标记它，并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时，那么从队列头取一个顶点，并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2，则搜索结束。
【题（poj 1101)】：给出一个地图，标有X的地方不能经过，给出一对坐标（2，3），（5，3），问这对坐标能否相连通（连连看），如果能则输出最少要经过的路段（路段是指一段直线，如果中途发生转折则就是两个路段）；如果不能则输出impossible。
http://dl.iteye.com/upload/attachment/0074/9374/90ba056e-bb2e-3434-9c9a-7665dd4b1093.jpg
【注意】：
（1）本题的路可以在在给定的地图外走，如：W=5，H=4，则可选的路范围为0<=w<=W+1，0<=h<=H+1；
另外注意每一组测试数据在输出结果后要输出一行空行
（2）只有一个注意点该题搜的不是最短路径，而是最少拐弯次数（类似于连连看），再者要处理好地图与坐标的关系。
Sample Input
http://dl.iteye.com/upload/attachment/0074/9870/9db98e2f-9643-335f-9369-16af168bac76.gif
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; } public Piece getGoal(){ return goal; } /* BFS访问与start最近的、相通（邻接）点并标记，路段数是1的是同一层，第一层完了再搜索第二层 路段数是2的是第二层，。。。（就一个四叉树而已）标记过的点不必再标记。*/ public void bfs(){ int i; Queue<Piece> que = new LinkedList<Piece>();que.add(start);//起点入队 visited = 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; temp2.y = temp1.y + dir; while(temp2.x>=0 && temp2.x<=h+1 && temp2.y>=0 && temp2.y<=w+1 && !visited &&g==' '){ //temp2与temp1相通 visited = true;//标记为已访问 temp2.step = temp1.step+1;//同一方向上相通的点，路段数相同。 que.add(new Piece(temp2.x,temp2.y,temp2.step));//入队 temp2.x += dir;//在同一方向上继续走 temp2.y += dir; } } }}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; for(int i=1; i<=h; ++i) { String line=in.nextLine(); for(int j=1; j<=w; j++) g=line.charAt(j-1);//地图 } nPacase = 0; //外围加框 for(int i=0; i<=w+1; i++) { g = ' '; g = ' '; } for(int i=0; i<=h+1; ++i) { g = ' '; g = ' '; } //测试图的正确性 /* for(int i=0; i<=h+1; i++) { for(int j=0; j<=w+1; j++) System.out.print(g); System.out.println(); }*/ System.out.println("Board #"+(++nCase)+":"); while(1==1) { char[][] c=new char; for(int i=0; i<=h+1; i++) { for(int j=0; j<=w+1; j++) c=g; //克隆数组 } 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 == 'X') { c = ' '; } 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(); } } }
下载源码：
页:
[1]