地下迷宫(bfs)

1.地下迷宫

思路：用广度优先搜索算法，即bfs，因为输入数据行数和列数为[3,10]，所在在搜索路径时，可以用x*10+y来表示其对应的坐标，并且将其加入对应的hash结点中。另一方面要求输出消耗最小的路径，所以队列使用优先级队列，保证每次从队列中取出的总是消耗最小的状态结点。而搜索时，防止重复搜索，用vis数组来表示是否已经访问过，并且访问时，如果出现越界或者能量值小于0时，可以不考虑这些状态结点

具体代码如下：

import java.util.Scanner;
import java.io.PrintWriter;
import java.io.FileInputStream;
import java.io.BufferedInputStream;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
public class Main implements Runnable
{
private Scanner cin;
private PrintWriter cout;
private boolean DEBUG =
true;
private int n, m, p;
private Map<Integer, StateNode> hm;
private Queue<StateNode> queue;
private int[][] matrix;
private boolean[][] vis;
private int[] dirx = {-1, 0, 1, 0};
private int[] diry = {0, 1, 0, -1};
private int[] dirp = {-3, -1, 0, -1};
class StateNode
{
int x, y, step, p, pre;
StateNode()
{
x = 0; y = 0; step = 0; p = 0; pre = -1;
}
StateNode(int x, int y, int step, int p, int pre)
{
this.x = x;
this.y = y;
this.step = step;
this.p = p;
this.pre = pre;
}
}
private void init()
{
try {
if (DEBUG) {
cin = new Scanner(new BufferedInputStream(new FileInputStream("f:\OJ\uva_in.txt")));
} else {
cin = new Scanner(new BufferedInputStream(System.in));
}
cout = new PrintWriter(new OutputStreamWriter(System.out));
} catch (IOException e) {
e.printStackTrace();;
}
}
private int hashVal(StateNode node)
{
return node.x * 10 + node.y;
}
private boolean isTarget(StateNode node)
{
return node.x == 0 && node.y == m - 1 && node.p >= 0;
}
private boolean is_impossible(int x, int y, int curp)
{
if (x < 0 || x >= n || y < 0 || y >= m || curp < 0 || matrix[x][y] == 0 || vis[x][y]) return true;
return false;
}
private boolean input()
{
if (!cin.hasNextInt()) return false;
n = cin.nextInt();
m = cin.nextInt();
p = cin.nextInt();
matrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = cin.nextInt();
}
}
return true;
}
private
void solve()
{
StateNode node = new StateNode(0, 0, 0, p, -1);
hm = new HashMap<>();
Comparator<StateNode> cmp = new Comparator<StateNode>() {
@Override
public int compare(StateNode o1, StateNode o2) {
return o2.p - o1.p;
}
};
queue = new PriorityQueue<StateNode>(cmp);
queue.add(node);
hm.put(hashVal(node), node);
vis = new boolean[n][m];
int ans = -1;
while (!queue.isEmpty()) {
StateNode cur_node = queue.poll();
if (isTarget(cur_node)) {
ans = hashVal(cur_node);
break;
}
vis[cur_node.x][cur_node.y] = true;
for (int i = 0; i < 4; i++) {
int new_x = cur_node.x + dirx[i];
int new_y = cur_node.y + diry[i];
int new_p = cur_node.p + dirp[i];
int new_step = cur_node.step + 1;
if (is_impossible(new_x, new_y, new_p)) continue;
StateNode new_node = new StateNode(new_x, new_y, new_step, new_p, hashVal(cur_node));
queue.add(new_node);
hm.put(hashVal(new_node), new_node);
}
}
if (ans == -1) {
cout.println("Can not escape!");
} else {
List<Integer> path = new ArrayList<>();
while (ans != -1) {
path.add(ans);
ans = hm.get(ans).pre;
}
for (int i = path.size() - 1; i >= 0; i--) {
cout.print("[" + Integer.toString(path.get(i) / 10) + "," + Integer.toString(path.get(i) % 10) + "]");
if (i != 0) cout.print(',');
}
}
cout.flush();
}
public void run()
{
init();
while (input())
{
solve();
}
}
public static void main(String[] args)
{
new Thread(new Main()).start();
}
}

最后

以上就是开放吐司为你收集整理的地下迷宫(bfs)的全部内容，希望文章能够帮你解决地下迷宫(bfs)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。