542. 01 矩阵
2021/12/17 23:50:45
本文主要是介绍542. 01 矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/01-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
多源广度优先搜索
import java.util.LinkedList; import java.util.Queue; class Solution { private int[] dx = {0, 1, 0, -1}; private int[] dy = {1, 0, -1, 0}; public int[][] updateMatrix(int[][] mat) { if (mat == null || mat.length == 0 || mat[0].length == 0) { return new int[0][0]; } int n = mat.length, m = mat[0].length; int[][] ret = new int[n][m]; Queue<Operation> queue = new LinkedList<>(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (mat[i][j] == 0) { queue.offer(new Operation(i, j, 0)); } } } while (!queue.isEmpty()) { Operation operation = queue.poll(); ret[operation.x][operation.y] = operation.step; for (int i = 0; i < 4; ++i) { int x = dx[i] + operation.x; int y = dy[i] + operation.y; if (x >= 0 && x < n && y >= 0 && y < m && mat[x][y] == 1) { queue.offer(new Operation(x, y, operation.step + 1)); mat[x][y] = 0; } } } return ret; } } class Operation { int x; int y; int step; public Operation(int x, int y, int step) { this.x = x; this.y = y; this.step = step; } }
动态规划
这篇关于542. 01 矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21订单系统资料入门教程:轻松管理你的订单
- 2024-09-21Java部署资料:新手入门教程
- 2024-09-21Java部署资料:新手入门教程
- 2024-09-21Java订单系统资料:新手入门教程与实战指南
- 2024-09-21Java管理系统资料入门教程
- 2024-09-21从零开始学习Java监控系统资料
- 2024-09-21Java就业项目资料:新手入门的必备教程
- 2024-09-21Java全端资料:初学者指南
- 2024-09-21Java全栈资料入门教程及资源汇总
- 2024-09-21Java日志系统资料入门教程