LeetCode 1091. Shortest Path in Binary Matrix
原题链接在这里:https://leetcode.com/problems/shortest-path-in-binary-matrix/
题目:
In an N by N square grid, each cell is either empty (0) or blocked (1).
A clear path from top-left to bottom-right has length k
if and only if it is composed of cells C_1, C_2, ..., C_k
such that:
- Adjacent cells
C_i
andC_{i+1}
are connected 8-directionally (ie., they are different and share an edge or corner) C_1
is at location(0, 0)
(ie. has valuegrid[0][0]
)C_k
is at location(N-1, N-1)
(ie. has valuegrid[N-1][N-1]
)- If
C_i
is located at(r, c)
, thengrid[r][c]
is empty (ie.grid[r][c] == 0
).
Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.
Example 1:
Input: [[0,1],[1,0]]
Output: 2
Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Note:
1 <= grid.length == grid[0].length <= 100
grid[r][c]
is0
or1
题解:
When doing BFS, for each level, mark the current size.
When polling current size node, pop up to next level.
If current polled node is bottom right node, return level.
Otherwise, for its 8 surrounding node, check if it is not visited nor block, add it to the queue.
Time Complexity: O(m*n). m = grid.length. n = grid[0].length.
Space: O(m*n).
AC Java:
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0){
return -1;
} int m = grid.length;
int n = grid[0].length;
if(grid[0][0] == 1 || grid[m-1][n-1] == 1){
return -1;
} LinkedList<int []> que = new LinkedList<>();
boolean [][] visited = new boolean[m][n];
visited[0][0] = true;
que.add(new int[]{0, 0}); int level = 1;
while(!que.isEmpty()){
int size = que.size();
while(size-->0){
int [] cur = que.poll();
if(cur[0] == m-1 && cur[1] == n-1){
return level;
} for(int i = -1; i<=1; i++){
for(int j = -1; j<=1; j++){
int x = cur[0]+i;
int y = cur[1]+j;
if(x<0 || x>=m || y<0 || y>=n || visited[x][y] || grid[x][y]==1){
continue;
} visited[x][y] = true;
que.add(new int[]{x, y});
}
}
} level++;
} return -1;
}
}
最新文章
- (转)JS产生随机数的几个用法!
- Twitter-Snowflake,64位自增ID算法详解
- Uva 1599 最佳路径
- codevs 1106 篝火晚会
- ANDROID开发之SQLite详解
- jquery手写焦点轮播图-------解决最后一张无缝跳转第一张的问题
- codevs3732 解方程
- javascript 我是广告
- polaris: 一个用go实现的支持restful的web框架
- 关于静态注册BroadcastReceiver接收不到广播的问题
- 改善python程序的建议[转]
- Coursera, Big Data 1, Introduction (week 1/2)
- 主从读写分离----mysql-proxy0.8.5安装与配置
- Weighted Channel Dropout for Regularization of Deep Convolutional Neural Network
- 差分约束系统+(矩阵)思维(H - THE MATRIX PROBLEM HDU - 3666 )
- 【tp5.1】通过PHPExcel实现导入excel表格
- mysql 主主架构,多入口 互为备份
- 【BZOJ4540】[Hnoi2016]序列 莫队算法+单调栈
- Perl参考函数/教程
- bufferedReader与StringReader
热门文章
- 【题解】最大 M 子段和 Max Sum Plus Plus [Hdu1024] [51nod1052]
- Dubbo面试踩坑
- JQuery的使用案例(二级联动,隔行换色,轮播图,广告插入)
- 计数计量单位KMGTPEZY【计算机】【天文】
- python自动备份阿里云数据库binlog
- Spring Security 解析(七) —— Spring Security Oauth2 源码解析
- FineReport连接ApacheKylin
- 函数内this指向+排序+找出数组大小项+Math类
- angularJS中select元素的应用浅析
- sweetalert 弹框简单使用