128kj 发表于 2013-2-3 10:16:04

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

广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 再依序拜访与刚才被拜访过的节点相邻但未曾被拜访过的节点,直到所有相邻的节点都已被拜访过。 因此,进行广搜 时,需要使用queue ,以便记录拜访的顺序。一般有下面的模板:
publicvoid bfs(int v) {//队列用来保存被访问节点的分支节点Queye< Integer> que = new LinkedList< Integer>();que.offer(v);//起点入队列while (!que.isEmpty()) {    v = que.poll();//弹出当前顶点    if(!visited){//如果当前顶顶点没有被访问过       System.out.print(v+"");//访问当前顶点       visited = true;//标记为已访问过    }   //将当前节点的分支节(邻接)点加入到队列中      for (int i = 0; i < k; i++) {       if (G == 1 && !visited) {que.add(i);       }      }    } }

对照这个模板,很容易解答下面两题.

例一:
   国际象棋,又称欧洲象棋或西洋棋,是一种二人对弈的战略棋盘游戏。国际象棋的棋盘由64个黑白相间的格子组成。黑白棋子各16个,多用木或塑胶制成,也有用石块制作;较为精美的石头、玻璃(水晶)或金属制棋子常用作装饰摆设。国际象棋是世界上最受欢迎的游戏之一,数以亿计的人们以各种方式下国际象棋。
    其中有一棋子,称为knight,和中国象棋里的马的走法一样,每次走都是一个 “日” 型。给定起始位置和目标位置,计算knight从起始位置走到目标位置所需的最少步数。
To get from xx to yy takes n knight moves.
从一点xx到另一点yy需要多少步,至少需要多少步 ??
http://dl.iteye.com/upload/attachment/0075/0191/cf6c45ba-67a6-3478-a3f5-2be6fcfe84f3.jpg

Sample Input

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.


import java.util.*;public class Main { //初始化马可以走的方向 private int dis[][]={{1,2},{2,1},{2,-1},{1,-2}, {-1,-2},{-2,-1},{-2,1},{-1,2}}; private int[][] chessboard ;//棋盘 public Main() {   chessboard = new int;   for(int i=0;i<8;i++)       Arrays.fill(chessboard,0); } privateint[] getRC(String s) {//用来处理输入,字符坐标转化为数字坐标int[] rc = new int;rc = Integer.valueOf(String.valueOf(s.charAt(1))) - 1;rc = s.charAt(0) - 'a';return rc; } /*** 广度搜索算法*   * @param s1* @param s2*/ publicvoid bsf(String s1, String s2) {//输出从s1到s2至少需要多少步int[] rc = getRC(s1);int formR = rc;int formC = rc;   //System.out.println(formR + " ," + formC);rc = getRC(s2);int toR = rc;int toC = rc;   //System.out.println(toR + " ," + toC);Queue< Point> queue = new LinkedList<Point>();Point p = new Point();p.r = formR;p.c = formC;p.steps = 0;queue.offer(p);//起点入队列chessboard = 1;//标记为已访问p = null;while (!queue.isEmpty()) {//队列非空时   p = queue.poll();//当前顶点   if (p.r == toR && p.c == toC) {//如果搜索到目标,输入    System.out.println("To get from " + s1 + " to " + s2      + " takes " + p.steps + " knight moves.");    break;   }   for (int i = 0; i < 8; ++i) {//从八个方向依次访问当前顶点的八个可能的邻接点    Point pp = new Point();    pp.r = p.r + dis;    pp.c = p.c + dis;    pp.steps = p.steps + 1;    if (pp.r >= 0 && pp.c >= 0 && pp.r <= 7 && pp.c <= 7      && chessboard == 0) {//如果是当前顶点的邻接点   queue.offer(pp);//邻接点入队列   chessboard = 1;//标记为已访问    }    pp = null;   }   p = null;} } public static void main(String[] args) {Scanner sc = new Scanner(System.in);   while (sc.hasNext()) {   String s1 = sc.next();   String s2 = sc.next();    new Main().bsf(s1, s2);} }}class Point { int r; int c; int steps;}

例二:农夫找牛(POJ 3278)
一个农场主为了找到自己走失的牛,要走最短的路径,只有三种走法:
x->x+1;
x->x-1;
x->2x;
    解释成数学问题: 给出2个数N和K(0 ≤ N ≤ 100,000,0 ≤ K ≤ 100,000),问从N经过+1或者-1或者*2能到达K的最小步数。

[分析]
   分3个方向BFS,找到后树的深度就是最小步数了。注意n可以比k大,这时只有-1一种办法可以从n到达k,直接减就行了.
import java.util.*;   public class Main {         public static final int MAX = 200000;         public static void main(String[] args) {             Scanner scan = new Scanner(System.in);         if (scan.hasNext()) {               int n = scan.nextInt();               int k = scan.nextInt();               System.out.println(catchTheCow(n, k));         }       }         public static int catchTheCow(int n, int k) {         //找到         if (n == k) {               return 0;         }         Queue< Integer> queue = new LinkedList<Integer>();         boolean[] visited = new boolean;         int[] minutes = new int;         visited = true;//标记起点已访问         queue.add(n);         while (!queue.isEmpty()) {               int current = queue.poll();//从队列中弹出当前点             for (int i = 0; i < 3; i++) {//依次访问当前点的邻接点               int next = current;                   //遍历3个方向                   if (i == 0) {                     next++;                   } else if (i == 1) {                     next--;                   } else if (i == 2) {                     next<<=1;                }                   if (next < 0 || next > MAX) {                     continue;                   }                   //剪枝保证每个数只进链表一次。                if (!visited) {                     queue.add(next);   //当前点的邻接点入队                  visited = true; //标记为已访问                      minutes = minutes + 1;                   }                   //找到                   if (next == k) {                     return minutes;                   }               }         }             return 0;       }   }程序运行:D:\tutu>javaMain5 174*/

下载源码:
页: [1]
查看完整版本: 广度优先搜索学习五例之三