当前位置:网站首页>Sword finger offer II 107 Distance in matrix
Sword finger offer II 107 Distance in matrix
2022-07-07 09:48:00 【PI Qiliang】
The finger of the sword Offer II 107. The distance in the matrix 【 Medium question 】
Ideas :
use BFS Sequence traversal , Find all the elements 0, From element 0 Start sequence traversal in four directions , set up ans The array stores the latest 0 distance , be ans in ,mat Matrix elements 0 The position value is 0, Encountered during traversal of each layer 1 Will ans Value is updated to element 0 Of ans value +1
Code :
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;
// Mark mat matrix (i,j) Whether the location element has been searched
boolean[][] seen = new boolean[m][n];
// Storage mat In the matrix 0 The position coordinates of
Queue<int[]> queue = new LinkedList<>();
// Storage mat matrix (i,j) The nearest location element 0 Distance of
ans = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0){
// take mat The elements in the matrix 0 The position coordinates of are pressed into the queue
queue.offer(new int[]{
i,j});
// The current location of the tag has been searched
seen[i][j] = true;
}
}
}
//BFS Traverse , When the element in the stack is empty , The loop ends
while(!queue.isEmpty()){
// Take out the top element of the queue 0 The location of
int[] cell = queue.poll();
// Take out the elements 0 Coordinates of
int i = cell[0],j = cell[1];
for (int k = 0; k < 4; k++) {
// The element 0 Search up, down, left and right , The location coordinates searched are (x,y)
int x = i + dir[k][0],y = j + dir[k][1];
// If (x,y) Does not exceed the matrix boundary and (x,y) The location has not been searched
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]){
//ans Of (x,y) Position value be equal to ans Of (i,j) Position value + 1
ans[x][y] = ans[i][j] + 1;
// take (x,y) Position push into queue
queue.offer(new int[]{
x,y});
// take (x,y) The location is marked as searched
seen[x][y] = true;
}
}
}
return ans;
}
}
边栏推荐
- [4g/5g/6g topic foundation-146]: Interpretation of white paper on 6G overall vision and potential key technologies-1-overall vision
- Octopus future star won a reward of 250000 US dollars | Octopus accelerator 2022 summer entrepreneurship camp came to a successful conclusion
- Gym - 102219j kitchen plates (violent or topological sequence)
- 在EXCEL写VBA连接ORACLE并查询数据库中的内容
- How to speed up video playback in browser
- Natapp intranet penetration
- 战略合作|SubQuery 成为章鱼网络浏览器的秘密武器
- 小程序滑动、点击切换简洁UI
- Database multi table Association query problem
- 如何使用clipboard.js库实现复制剪切功能
猜你喜欢
数据建模中利用3σ剔除异常值进行数据清洗
Unity uses mesh to realize real-time point cloud (I)
【frida实战】“一行”代码教你获取WeGame平台中所有的lua脚本
JS reverse tutorial second issue - Ape anthropology first question
Unity3d interface is embedded in WPF interface (mouse and keyboard can respond normally)
AI从感知走向智能认知
[4G/5G/6G专题基础-146]: 6G总体愿景与潜在关键技术白皮书解读-1-总体愿景
第一讲:包含min函数的栈
JS逆向教程第一发
Switching value signal anti shake FB of PLC signal processing series
随机推荐
[4g/5g/6g topic foundation-146]: Interpretation of white paper on 6G overall vision and potential key technologies-1-overall vision
2016 CCPC Hangzhou Onsite
Difference between process and thread
Arthas simple instructions
How to speed up video playback in browser
沙龙预告|GameFi 领域的瓶颈和解决方案
细说Mysql MVCC多版本控制
CentOS installs JDK1.8 and mysql5 and 8 (the same command 58 in the second installation mode is common, opening access rights and changing passwords)
**Grafana installation**
Netease cloud wechat applet
洛谷P2482 [SDOI2010]猪国杀
Unity uses mesh to realize real-time point cloud (II)
用flinksql的方式 写进 sr的表,发现需要删除的数据没有删除,参照文档https://do
第十四次试验
[Frida practice] "one line" code teaches you to obtain all Lua scripts in wegame platform
Oracle安装增强功能出错
Software modeling and analysis
How to become a senior digital IC Design Engineer (5-3) theory: ULP low power design technology (Part 2)
PLC信号处理系列之开关量信号防抖FB
Impression notes finally support the default markdown preview mode