当前位置:网站首页>剑指 Offer II 107. 矩阵中的距离
剑指 Offer II 107. 矩阵中的距离
2022-07-07 07:07:00 【彼淇梁】
剑指 Offer II 107. 矩阵中的距离【中等题】
思路:
采用BFS层序遍历,找出所有的元素0,从元素0开始向四个方向层序遍历,设ans数组存储最近0距离,则ans中,mat矩阵元素0位置值为0,每层遍历遇到1则将ans值更新为元素0的ans值+1
代码:
class Solution {
static int[][] ans;
static int[][] dir = {
{
0,-1},{
0,1},{
-1,0},{
1,0}};
static int m,n;
public static int[][] updateMatrix(int[][] mat) {
m = mat.length;
n = mat[0].length;
//标记mat矩阵(i,j)位置元素是否被搜索过
boolean[][] seen = new boolean[m][n];
//存储mat矩阵中的0的位置坐标
Queue<int[]> queue = new LinkedList<>();
//存储mat矩阵(i,j)位置元素最近的0的距离
ans = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0){
//将mat矩阵中元素0的位置坐标压入队列
queue.offer(new int[]{
i,j});
//标记当前位置已被搜索过
seen[i][j] = true;
}
}
}
//BFS遍历,当栈中元素为空时,循环结束
while(!queue.isEmpty()){
//取出队列顶部元素0的位置
int[] cell = queue.poll();
//取出元素0的坐标
int i = cell[0],j = cell[1];
for (int k = 0; k < 4; k++) {
//对元素0进行上下左右四个方向搜索,搜索到的位置坐标为(x,y)
int x = i + dir[k][0],y = j + dir[k][1];
//如果(x,y)未超出矩阵边界且(x,y)位置未被搜索过
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]){
//ans的(x,y)位置值 等于 ans的(i,j)位置值 + 1
ans[x][y] = ans[i][j] + 1;
//将(x,y)位置压入队列
queue.offer(new int[]{
x,y});
//将(x,y)位置标记为已搜索
seen[x][y] = true;
}
}
}
return ans;
}
}
边栏推荐
- sql 里面使用中文字符判断有问题,哪位遇到过?比如value&lt;&gt;`无`
- 網易雲微信小程序
- Arthas simple instructions
- Add new item after the outbound delivery order of SAP mm sto document is created?
- H5 web player easyplayer How does JS realize live video real-time recording?
- Information Security Experiment 1: implementation of DES encryption algorithm
- Huawei HCIP - datacom - Core 03 jours
- How to become a senior digital IC Design Engineer (5-2) theory: ULP low power design technology (Part 1)
- Lesson 1: hardness of eggs
- The use of recycling ideas
猜你喜欢
Esp8266 uses TF card and reads and writes data (based on Arduino)
细说Mysql MVCC多版本控制
How will fashion brands enter the meta universe?
華為HCIP-DATACOM-Core_03day
章鱼未来之星获得25万美金奖励|章鱼加速器2022夏季创业营圆满落幕
Vs2013 generate solutions super slow solutions
Unity shader (to achieve a simple material effect with adjustable color attributes only)
Octopus future star won a reward of 250000 US dollars | Octopus accelerator 2022 summer entrepreneurship camp came to a successful conclusion
嵌套(多级)childrn路由,query参数,命名路由,replace属性,路由的props配置,路由的params参数
Integer or int? How to select data types for entity classes in ORM
随机推荐
Yapi test plug-in -- cross request
Netease cloud wechat applet
信息安全实验三 :PGP邮件加密软件的使用
Information Security Experiment 1: implementation of DES encryption algorithm
[bw16 application] Anxin can realize mqtt communication with bw16 module / development board at instruction
shake数据库中怎么使用Mongo-shake实现MongoDB的双向同步啊?
MongoDB怎么实现创建删除数据库、创建删除表、数据增删改查
js逆向教程第二发-猿人学第一题
JS judge whether checkbox is selected in the project
JS逆向教程第一发
IIS redirection redirection appears eurl axd
印象笔记终于支持默认markdown预览模式
Unity uses mesh to realize real-time point cloud (I)
Detailed explanation of diffusion model
Database multi table Association query problem
Zen - batch import test cases
进程间的通信方式
sql 里面使用中文字符判断有问题,哪位遇到过?比如value&lt;&gt;`无`
华为HCIP-DATACOM-Core_03day
Jenkins automated email