题目请参考:PTA7-1 迷宫寻路 (20分)
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static final Scanner input = new Scanner(System.in);
public static void main(String[] args) {
for (;;) {
int row = input.nextInt();
if (row < 0) {
break;
}
Maze maze = new Maze(row, input.nextInt());
if (maze.process()) {
Maze.Node now = maze.goal;
StringBuilder sb = new StringBuilder();
while (now != null) {
sb.insert(0, now.forPrint());
now = now.from;
}
System.out.println(sb);
} else {
System.out.println("NO FOUND");
}
}
}
static class Maze {
int row;
int col;
Node[][] maze;
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing(Node::f));
Node goal;
class Node {
final int x;
final int y;
int g;
final int h;
Node from;
boolean closed;
Node(int x, int y) {
this.x = x;
this.y = y;
h = Math.abs(x - row) + Math.abs(y - col);
}
int f() {
return g + h;
}
void setParent(Node parent) {
g = parent.g + 1;
from = parent;
}
String forPrint() {
return (x + 1) + "," + (y + 1) + System.lineSeparator();
}
void addToClose() {
closed = true;
}
}
Maze(int row, int col) {
this.row = row;
this.col = col;
maze = new Node[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (input.nextInt() == 0) {
maze[i][j] = new Node(i, j);
}
}
}
goal = maze[row - 1][col - 1];
}
boolean process() {
if (maze[0][0] != null) {
open.add(maze[0][0]);
}
while (!open.isEmpty()) {
Node parent = open.poll();
if (parent == goal) {
return true;
}
parent.addToClose();
spread(parent);
}
return false;
}
void spread(Node parent) {
int x = parent.x;
int y = parent.y;
trySpread(parent, x - 1, y);
trySpread(parent, x + 1, y);
trySpread(parent, x, y - 1);
trySpread(parent, x, y + 1);
}
void trySpread(Node parent, int childX, int childY) {
if (childX < 0 || childX == row || childY < 0 || childY == col) {
return;
}
Node child = maze[childX][childY];
if (child == null || child.closed) {
return;
}
if (open.contains(child)) {
if (parent.g + 1 < child.g) {
child.setParent(parent);
}
} else {
child.setParent(parent);
open.add(child);
}
}
}
}