java - 关于 leetcode 1091 二进制矩阵中最短路径的问题
问题描述
我试图使用启发式算法和优先级队列来解决二进制矩阵中的 leetcode 1091 最短路径。但是,我无法通过所有测试。您对我的代码中的错误有任何想法吗?
例如,输入是 [[0,0,0],[1,1,0],[1,1,0]],输出应该是 4。但是,我的代码得到的输出是 5。启发式我使用的是当前节点到目标节点之间的直接距离。
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int side_length = grid.length;
// if the s left top corner is 1 then, no path exist and return -1
if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1)
{
return -1;
}
if(side_length == 1)
{
return 1;
}
// 2D array for 8 directions
int[][] directions = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
PriorityQueue<Node> pqueue = new PriorityQueue<Node>(10, new Comparator<Node>()
{
public int compare(Node i, Node j) {
if(Double.compare(i.heuristic, j.heuristic) < 0){
return 100;
}
else
{
return -100;
}
}
});
double heuristic = e_distance(0, 0, side_length - 1, side_length - 1);
Node start_point = new Node(0, 0, heuristic);
pqueue.add(start_point);
boolean explored[][] = new boolean[side_length][side_length];
explored[0][0] = true;
int output = 1;
while(!pqueue.isEmpty())
{
Node curr_point = pqueue.poll();
int x = curr_point.x;
int y = curr_point.y;
explored[x][y] = true;
if(x == side_length - 1 && y == side_length - 1)
{
return output;
}
for(int[] successor : directions)
{
int successor_x = x + successor[0];
int successor_y = y + + successor[1];
heuristic = e_distance(successor_x, successor_y, side_length - 1, side_length - 1);
Node successor_point = new Node(successor_x, successor_y, heuristic);
if (pqueue.contains(successor_point))
{
continue;
}
if(successor_x >= 0 && successor_x < side_length && successor_y >= 0
&& successor_y < side_length && grid[successor_x][successor_y] == 0
&& !explored[successor_x][successor_y])
{
if(successor_x == side_length - 1 && successor_y == side_length - 1)
{
return output + 1;
}
pqueue.add(successor_point);
}
else
{
continue;
}
}
output++;
}
return -1;
}
public double e_distance(int x, int y, int target_x, int target_y)
{
return Math.sqrt(Math.abs(target_x - x) * Math.abs(target_x - x) + Math.abs(target_y - y)* Math.abs(target_y - y));
}
}
public class Node{
public int x;
public int y;
public double heuristic;
public Node(int x, int y, double heuristic)
{
this.x = x;
this.y = y;
this.heuristic = heuristic;
}
}
解决方案
以下是基于您的代码的BFS解决方案。尽管可能需要进一步调试,但它正在工作:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
List<int[][]>grids = new ArrayList<>();
grids.add( new int[][] {{0,1},{1,0}} );//2
grids.add( new int[][]{{0,0,0},{1,1,0},{1,1,0}} ); //4
grids.add( new int[][] {{1,0,0},{1,1,0},{1,1,0}} );//-1
Solution s = new Solution();
for (int[][]grid : grids) {
System.out.println(s.shortestPathBinaryMatrix(grid));
}
}
}
class Solution {
// 2D array for 8 directions
public static int[][] DIRECTIONS = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
public int shortestPathBinaryMatrix(int[][] grid) {
int side_length = grid.length;
// if the s left top corner is 1 then, no path exist and return -1
if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1) return -1;
if(side_length == 1) return 1;
Queue<Node> pqueue = new LinkedList<>();
Node start_point = new Node(0, 0);
pqueue.add(start_point);
boolean explored[][] = new boolean[side_length][side_length];//you can use grid values to mark explored
//int output = 1; use Node.parent to mark the path
while(!pqueue.isEmpty()){
Node curr_point = pqueue.poll();
int x = curr_point.x;
int y = curr_point.y;
explored[x][y] = true;
if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);
for(int[] successor : DIRECTIONS) {
int successor_x = x + successor[0];
int successor_y = y + + successor[1];
Node successor_point = new Node(successor_x, successor_y);
if (pqueue.contains(successor_point))
{
continue;
}
if(successor_x >= 0 && successor_x < side_length && successor_y >= 0
&& successor_y < side_length
&& grid[successor_y][successor_x] == 0 //NOT grid[successor_x][successor_y] == 0
&& !explored[successor_x][successor_y])
{
//if(successor_x == side_length - 1 && successor_y == side_length - 1)
// return output + 1;
explored[successor_x][successor_y] = true; //mark as explored
successor_point.setParent(curr_point); //mark as child of current node
pqueue.add(successor_point);
}
else //this else does nothing
{
continue;
}
}
}
return -1;
}
private int pathLength(Node node) {
if(node == null) return 0;
int pathLength = 1;
while (node.getParent() !=null){
node = node.getParent();
pathLength++;
}
return pathLength;
}
}
class Node{
public int x, y;
public double cost;
public Node parent = null;
public Node(int x, int y){
this(x, y, 0);
}
public Node(int x, int y, double cost)
{
this.x = x; this.y = y;
this.cost = cost;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
//todo implement equals and hashCode
}
一个更好的实施shortestPathBinaryMatrix
:
public int shortestPathBinaryMatrix(int[][] grid) {
int side_length = grid.length;
// if the s left top corner is 1 then, no path exist and return -1
if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1) return -1;
if(side_length == 1) return 1;
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(0, 0));
while(!queue.isEmpty()){
Node curr_point = queue.poll();
int x = curr_point.x; int y = curr_point.y;
if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);
grid[y][x] = 1;
for(int[] successor : DIRECTIONS) {
int successor_x = x + successor[0];
int successor_y = y + + successor[1];
if(successor_x >= 0 && successor_x < side_length && successor_y >= 0
&& successor_y < side_length
&& grid[successor_y][successor_x] == 0) {
Node successor_point = new Node(successor_x, successor_y);
if (queue.contains(successor_point)){
continue;
}
grid[successor_y][successor_x] = 1; //mark as explored
successor_point.setParent(curr_point); //mark as child of current node
queue.add(successor_point);
}
}
}
return -1;
}
当不同的边有不同的成本(加权图)时,您可能需要实现Dijkstra算法。Dijkstra 算法基本上是一种增强的 BFS。这是成本和PriorityQueue
需要的地方。
shortestPathBinaryMatrix
变成:
//Dijkstra's Algorithm
public int shortestPathBinaryMatrix(int[][] grid) {
int side_length = grid.length;
// if the s left top corner is 1 then, no path exist and return -1
if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1) return -1;
if(side_length == 1) return 1;
PriorityQueue<Node> queue = new PriorityQueue<>(10,(i,j)-> Double.compare(i.cost, j.cost));
queue.add(new Node(0, 0, 0));
while(!queue.isEmpty()){
Node curr_point = queue.poll();
int x = curr_point.x; int y = curr_point.y;
if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);
grid[y][x] = 1;
for(int[] successor : DIRECTIONS) {
int successor_x = x + successor[0];
int successor_y = y + + successor[1];
if(successor_x >= 0 && successor_x < side_length
&& successor_y >= 0 && successor_y < side_length
&& grid[successor_y][successor_x] == 0) {
double cost = curr_point.cost+1;
Node successor_point = new Node(successor_x, successor_y, cost);
if (queue.contains(successor_point)) {
continue;
}
grid[successor_y][successor_x] = 1; //mark as explored
successor_point.setParent(curr_point); //mark as child of current node
queue.add(successor_point);
}
}
}
return -1;
}
实现A * 算法时需要启发式。A* 算法基本上是一种增强的 Dijkstra 算法。
要实现它,您只需要将成本计算修改为:
double cost = curr_point.cost+1 + heuristic ;
因此shortestPathBinaryMatrix
变为:
//A* algorithm
public int shortestPathBinaryMatrix(int[][] grid) {
int side_length = grid.length;
// if the s left top corner is 1 then, no path exist and return -1
if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1) return -1;
if(side_length == 1) return 1;
PriorityQueue<Node> queue = new PriorityQueue<>(10,(i,j)-> Double.compare(i.cost, j.cost));
queue.add(new Node(0, 0, 0));
while(!queue.isEmpty()){
Node curr_point = queue.poll();
int x = curr_point.x; int y = curr_point.y;
if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);
grid[y][x] = 1;
for(int[] successor : DIRECTIONS) {
int successor_x = x + successor[0];
int successor_y = y + + successor[1];
if(successor_x >= 0 && successor_x < side_length
&& successor_y >= 0 && successor_y < side_length
&& grid[successor_y][successor_x] == 0) {
double cost = curr_point.cost+1 + distance(successor_x, successor_y, x, y);
Node successor_point = new Node(successor_x, successor_y, cost);
if (queue.contains(successor_point)) {
continue;
}
grid[successor_y][successor_x] = 1; //mark as explored
successor_point.setParent(curr_point); //mark as child of current node
queue.add(successor_point);
}
}
}
return -1;
}
并distance
定义为:
public double distance(int x, int y, int targetX, int targetY) {
return Math.sqrt(Math.pow(targetX - x,2) + Math.pow(targetY - y,2));
}
推荐阅读
- python - 在排序一个列表期间将不同列表中的相关元素保持在一起
- c# - 如何对通用列表对象进行排序
- javascript - 向和从 js 服务器发送数据的基本方法?
- json - 使用 Pyspark 处理 JSON 结构
- amazon-web-services - 为什么角色假设应该在 lambda 内部完成?
- html - 如何将数值绑定到 CSS 以创建时间线?
- docker - 如何为 docker compose 环境变量设置运行时变量
- javascript - 仅在 Javascript 中具有不同段落的动态 Div
- tsql - 表格模型中的测量列未在浏览器中显示正确的值
- javascript - 调用此函数时如何获取返回值?