[LC] 505. The Maze II
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
class Solution {
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int row = maze.length;
int col = maze[0].length;
int res = 0;
Queue<Cell> queue = new LinkedList<>();
int[][] dists = new int[row][col];
for (int[] dist: dists) {
Arrays.fill(dist, -1);
}
queue.offer(new Cell(start[0], start[1]));
dists[start[0]][start[1]] = 0;
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int size = queue.size();
Cell cur = queue.poll();
int curX = cur.x;
int curY = cur.y; for (int[] direction: directions) {
int newX = curX;
int newY = curY;
int curDist = dists[curX][curY]; while (newX >= 0 && newX < row && newY >= 0 && newY < col && maze[newX][newY] == 0) {
newX += direction[0];
newY += direction[1];
curDist += 1;
}
newX -= direction[0];
newY -= direction[1];
curDist -= 1;
if (dists[newX][newY] == -1 || curDist < dists[newX][newY]) {
dists[newX][newY] = curDist;
queue.offer(new Cell(newX, newY));
}
} }
return dists[destination[0]][destination[1]];
}
} class Cell {
int x;
int y;
public Cell(int x, int y) {
this.x = x;
this.y = y;
}
}
最新文章
- The property on could not be set to a &#39;Int16&#39; value.You must set this property to a non-null value of type ‘Int32’.”
- ListView和ScrollView冲突
- 百度前端技术学院(IFE)2016春季学期总结
- js中取session的值
- Android 打开系统最近任务及最近应用方法
- 解决tomcat运行报错java.lang.UnsatisfiedLinkError: apache-tomcat-7.0.37\bin\tcnative-1.dll:Can load AMD 64
- idea/eclipse下Maven工程集成web服务(tomcat、jetty)
- [转]PostgreSQL数据类型
- qt delete
- MyBatis基础:MyBatis调用存储过程(6)
- [PHP] PHP闭包(closures)
- Qt5应用改变窗口大小时出现黑影
- Mysql建库建用户建表等常用命令
- [原]CentOS7安装Rancher2.1并部署kubernetes (一)---部署Rancher
- Codeforces 950 C. Zebras
- Android 1.6 PackageParser.java 源码分析
- [Linux 003]——用户和用户组以及 Linux 权限管理(一)
- spring boot热部署pom.xml配置
- AWS系列-AWS EC2实例类型改配(机器配置升级)
- 灾难恢复:RPO与RTO