本文主要是介绍oj acm 1026 广度搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最短距离求解
求解最短距离，使用广度优先搜索和优先队列结合
使用visted数组记录是该层某节点否访问过。由于是保存在优先队列中，只要该层前面的路径有访问该节点，则一定是到达该节点的最短距离。
使用flag数组记录从某节点到达x,y的方向，从而输出时能还原路径。
代码
import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.Scanner;//广度优先
class Pos implements Comparable {private int x;private int y;private int step;public int getX() {return x;}public void setX(int x) {this.x = x;}public int getY() {return y;}public void setY(int y) {this.y = y;}public int getStep() {return step;}public void setStep(int step) {this.step = step;}@Overridepublic String toString() {return "Pos{" +"x=" + x +", y=" + y +", step=" + step +'}';}public Pos(int x, int y, int step) {this.x = x;this.y = y;this.step = step;}public Pos() {}@Overridepublic int compareTo(Object o) {//从小到大if (o instanceof Pos) {Pos p = (Pos) o;return this.step - p.step;}return 0;}
}public class Main_1026 {private static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};private static int n, m;private static int count;private static PriorityQueue<Pos> result;private static int[][] flag;private static boolean[][] visited;private static char[][] c;public static void main(String[] args) throws FileNotFoundException {Scanner in = new Scanner(new File("src/input.txt"));while (in.hasNext()) {n = in.nextInt();m = in.nextInt();count = 0;result = new PriorityQueue<>();flag = new int[n][m];visited = new boolean[n][m];c = new char[n][m];for (int i = 0; i < n; i++) {String s = in.next();for (int j = 0; j < m; j++) {c[i][j] = s.charAt(j);}}int step = c[0][0]=='.'? 0 : c[0][0] -'0';result.add(new Pos(0, 0, step));visited[0][0]= true;int count = bfs();if(count != -1) {System.out.println("It takes "+count+" seconds to reach the target position, let me show you the way.");print(n-1,m-1);}else{System.out.println("God please help our poor hero.");}System.out.println("FINISH");}}public static int bfs() {while (!result.isEmpty()) {Pos pre = result.poll();if (pre.getX() == n - 1 && pre.getY() == m - 1) {return pre.getStep();}for (int i = 0; i < 4; i++) {int x = pre.getX() + dir[i][0];int y = pre.getY() + dir[i][1];if (isValid(x, y)) {int step = c[x][y]=='.'? 1: c[x][y]-'0'+1;Pos next = new Pos(x, y, pre.getStep()+step);visited[x][y] = true;flag[x][y] = i + 1;result.add(next);}}}return -1;}public static void print(int x, int y) {if (flag[x][y] == 0) {if(c[x][y] !='.'){while(c[x][y]-'0'>=1){count++;c[x][y]--;System.out.printf("%ds:FIGHT AT (%d,%d)\n", count, x, y);}}return;}int pre_x = x - dir[flag[x][y] - 1][0];int pre_y = y - dir[flag[x][y] - 1][1];print(pre_x, pre_y);count++;System.out.printf("%ds:(%d,%d)->(%d,%d)\n", count, pre_x, pre_y, x, y);while (c[x][y] != '.' && c[x][y] - '0' >= 1) {count++;c[x][y]--;System.out.printf("%ds:FIGHT AT (%d,%d)\n", count, x, y);}}public static boolean isValid(int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m) {return false;}if (c[x][y] == 'X') {return false;}if(visited[x][y]){return false;}return true;}
}
这篇关于oj acm 1026 广度搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
