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

   广度优先搜索是以某一节点为出发点，先拜访所有相邻的节点。 再依序拜访与刚才被拜访过的节点相邻但未曾被拜访过的节点，直到所有相邻的节点都已被拜访过。 因此，进行广搜 时，需要使用queue ，以便记录拜访的顺序。一般有下面的模板:

public  void bfs(int v) {
  //队列用来保存被访问节点的分支节点
  Queye< Integer> que = new LinkedList< Integer>();
  que.offer(v);//起点入队列
  while (!que.isEmpty()) {
    v = que.poll();//弹出当前顶点
    if(!visited[v]){//如果当前顶顶点没有被访问过
       System.out.print(v+"  ");//访问当前顶点
       visited[v] = true;//标记为已访问过
    }
     //将当前节点的分支节(邻接）点加入到队列中
      for (int i = 0; i < k; i++) {
       if (G[v][i] == 1 && !visited[i]) {
	que.add(i);
       }
      }
    }
 }

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

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


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[8][8];
     for(int i=0;i<8;i++)
       Arrays.fill(chessboard[i],0);
 }


 private  int[] getRC(String s) {//用来处理输入，字符坐标转化为数字坐标
  int[] rc = new int[2];
  rc[0] = Integer.valueOf(String.valueOf(s.charAt(1))) - 1;
  rc[1] = s.charAt(0) - 'a';
  return rc;
 }

 /**
  * 广度搜索算法
  * 
  * @param s1
  * @param s2
  */
 public  void bsf(String s1, String s2) {//输出从s1到s2至少需要多少步
  int[] rc = getRC(s1);
  int formR = rc[0];
  int formC = rc[1];
   //System.out.println(formR + " ," + formC);
  rc = getRC(s2);
  int toR = rc[0];
  int toC = rc[1];
   //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[p.r][p.c] = 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[i][0];
    pp.c = p.c + dis[i][1];
    pp.steps = p.steps + 1;
    if (pp.r >= 0 && pp.c >= 0 && pp.r <= 7 && pp.c <= 7
      && chessboard[pp.r][pp.c] == 0) {//如果是当前顶点的邻接点
     queue.offer(pp);//邻接点入队列
     chessboard[pp.r][pp.c] = 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[MAX + 5];   
        int[] minutes = new int[MAX + 5];   
        visited[n] = 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[next]) {   
                    queue.add(next);   //当前点的邻接点入队
                    visited[next] = true; //标记为已访问  
                    minutes[next] = minutes[current] + 1;   
                }   
                //找到   
                if (next == k) {   
                    return minutes[k];   
                }   
            }   
        }   
  
        return 0;   
    }   
}  
程序运行:
D:\tutu>java  Main
5 17
4
*/

下载源码: