输入一个5x5的字符矩阵表示的绝地求生地图，每个数字字符表示该区域敌人的数量，*字符表示跳伞点，#表示目标点，求玩家从跳伞点到目标点最少需要遭遇多少个敌人。
import java.util.Scanner;
/*
绝地求生 寻路算法 地图
3 2 1 # 9
3 3 0 3 2
1 9 5 3 2
2 0 1 1 *
2 5 4 5 4
*/
public class Main {
//地图尺寸5
static final int MAP_SIZE = 5;
//节点数（邻接矩阵长）5*5
static final int GRAPH_SIZE = MAP_SIZE * MAP_SIZE;
//起始点
static final String START_CHAR = "*";
//目标点
static final String END_CHAR = "#";
//地图数组
static int[][] game_map = new int[MAP_SIZE][MAP_SIZE];
//最短路径数组
static int[] dist = new int[GRAPH_SIZE];
//最短路径上一跳数组
static int[] path = new int[GRAPH_SIZE];
//节点最短路径求解状态数组
static boolean[] fin = new boolean[GRAPH_SIZE];
//起始点索引
static int start;
//目标点索引
static int end;
public static void main(String args[]) {
dijkstra();
}
public static void init() {
Scanner sc = new Scanner(System.in);
String[] blocks;
int index;
String node;
//初始化顶点数组
for (int i = 0; i < GRAPH_SIZE; i++) {
dist[i] = path[i] = -1;
fin[i] = false;
}
//逐行读取数组
for (int i = 0; i < MAP_SIZE; i++) {
//行分割成块
blocks = sc.nextLine().trim().split(" ");
//逐块处理顶点
for (int j = 0; j < MAP_SIZE; j++) {
//顶点索引
index = i * MAP_SIZE + j;
//顶点值
node = blocks[j];
if (node.equals(START_CHAR)) { //初始化起始点
start = index;
dist[index] = 0;
game_map[i][j] = 0;
} else if (node.equals(END_CHAR)) { //初始化目标点
end = index;
game_map[i][j] = 0;
} else { //初始化其他点
game_map[i][j] = Integer.parseInt(node);
}
}
}
}
public static void dijkstra() {
init();
int current_node = start, min_dist, map_x, map_y;
for (int x = 0; x < GRAPH_SIZE; x++) {
min_dist = Integer.MAX_VALUE;
//求出未求解顶点中距起点最近的点
for (int i = 0; i < GRAPH_SIZE; i++) {
if (!fin[i] && dist[i] > -1 && dist[i] < min_dist) {
current_node = i;
min_dist = dist[i];
}
}
//标记该点为已求解
fin[current_node] = true;
int current_y = current_node % MAP_SIZE;
//更新与current_node相连的未求解点的最短路径
for (int i = 0; i < GRAPH_SIZE; i++) {
//计算i点的y坐标
map_y = i % MAP_SIZE;
if ((map_y == current_y + 1 && i == current_node + 1) || (map_y == current_y - 1 && i == current_node - 1) || i == current_node + MAP_SIZE || i == current_node - MAP_SIZE) { //如果在图中相连
if (!fin[i]) { //如果是未求解点
//计算i点的x坐标
map_x = (i - map_y) / MAP_SIZE;
//计算i点经current_node到起始点的距离
map_x = dist[current_node] + game_map[map_x][map_y];
if (dist[i] < 0 || dist[i] > map_x) { //如果经current_node可以连通起始点和i点且距离更近
dist[i] = map_x;
path[i] = current_node;
}
}
}
}
}
System.out.println(dist[end]);
}
}
该算法的时间复杂度为O(n^2)，通过小顶堆可以将每次寻找未求解顶点中距起点最近的点的时间复杂度降为O(logn)，而更新与current_node相连的未求解点的最短路径可以以O(1)时间复杂度实现（因为每个顶点最多与上下左右4个顶点相连），所以整个算法时间复杂度可以优化为O(nlogn)，Java中可以使用PriorityQueue实现。
import java.util.*;
/*
绝地求生 寻路算法 地图
3 2 1 # 9
3 3 0 3 2
1 9 5 3 2
2 0 1 1 *
2 5 4 5 4
*/
public class Main {
//地图尺寸5
private static final int MAP_SIZE = 5;
//节点数（邻接矩阵长）5*5
private static final int GRAPH_SIZE = MAP_SIZE * MAP_SIZE;
//起始点
private static final String START_CHAR = "*";
//目标点
private static final String END_CHAR = "#";
// 顶点数组
private static ArrayList<GraphNode> nodeList = new ArrayList<>();
//待排序堆
private static PriorityQueue<GraphNode> nodeHeap = new PriorityQueue<>();
//目标点
private static GraphNode end;
public static void main(String args[]) {
dijkstra();
}
public static void init() {
int index;
String node;
String[] blocks;
Scanner sc = new Scanner(System.in);
nodeList.clear();
nodeHeap.clear();
//逐行读取数组
for (int i = 0; i < MAP_SIZE; i++) {
//行分割成块
blocks = sc.nextLine().trim().split(" ");
//逐块处理顶点
for (int j = 0; j < MAP_SIZE; j++) {
GraphNode gnode = new GraphNode();
nodeList.add(gnode);
//顶点值
node = blocks[j];
if (node.equals(START_CHAR)) { //初始化起始点
gnode.dist = 0;
} else if (node.equals(END_CHAR)) { //初始化目标点
end = gnode;
} else { //初始化其他点
gnode.weight = Integer.parseInt(node);
}
}
}
for (int i = 0; i < nodeList.size(); i++) {
GraphNode gnode = nodeList.get(i);
index = (i % MAP_SIZE);
if (index < MAP_SIZE - 1) {
gnode.targets.add(nodeList.get(i + 1));
}
if (index > 0) {
gnode.targets.add(nodeList.get(i - 1));
}
if (i < GRAPH_SIZE - MAP_SIZE) {
gnode.targets.add(nodeList.get(i + MAP_SIZE));
}
if (i >= MAP_SIZE) {
gnode.targets.add(nodeList.get(i - MAP_SIZE));
}
nodeHeap.add(gnode);
}
}
public static void dijkstra() {
init();
int weight;
while (!nodeHeap.isEmpty()) {
GraphNode gnode = nodeHeap.poll();
if (gnode == end) {
break;
}
gnode.fin = true;
for (GraphNode tnode : gnode.targets) {
weight = gnode.dist + tnode.weight;
if (!tnode.fin && tnode.dist > weight) {
tnode.dist = weight;
tnode.path = gnode;
}
}
}
System.out.println(end.dist);
}
}
class GraphNode implements Comparable {
List<GraphNode> targets = new ArrayList<>();
GraphNode path = null;
int dist = Integer.MAX_VALUE >> 1; //不要用MAX_VALUE，否则在计算gnode.dist + tnode.weight时会溢出
int weight = 0;
boolean fin = false;
@Override
public int compareTo(Object o) {
return dist - ((GraphNode) o).dist;
}
}
网友评论