广度优先搜索学习五例之三
广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 再依序拜访与刚才被拜访过的节点相邻但未曾被拜访过的节点,直到所有相邻的节点都已被拜访过。 因此,进行广搜 时,需要使用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]