【leetcode】1030. Matrix Cells in Distance Order
2024-09-05 14:07:06
题目如下:
We are given a matrix with
R
rows andC
columns has cells with integer coordinates(r, c)
, where0 <= r < R
and0 <= c < C
.Additionally, we are given a cell in that matrix with coordinates
(r0, c0)
.Return the coordinates of all cells in the matrix, sorted by their distance from
(r0, c0)
from smallest distance to largest distance. Here, the distance between two cells(r1, c1)
and(r2, c2)
is the Manhattan distance,|r1 - r2| + |c1 - c2|
. (You may return the answer in any order that satisfies this condition.)Example 1:
Input: R = 1, C = 2, r0 = 0, c0 = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (r0, c0) to other cells are: [0,1]Example 2:
Input: R = 2, C = 2, r0 = 0, c0 = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.Example 3:
Input: R = 2, C = 3, r0 = 1, c0 = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].Note:
1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
解题思路:BFS,就这样。
代码如下:
class Solution(object):
def allCellsDistOrder(self, R, C, r0, c0):
"""
:type R: int
:type C: int
:type r0: int
:type c0: int
:rtype: List[List[int]]
"""
visit = []
for i in range(R):
visit.append([0] * C)
direction = [(1,0),(-1,0),(0,1),(0,-1)]
queue = [(r0,c0)]
res = []
while len(queue) > 0:
x,y = queue.pop(0)
if visit[x][y] == 1:
continue
res.append([x, y])
visit[x][y] = 1
for (i,j) in direction:
if x + i >= 0 and x + i < R and y + j >=0 and y+j < C and visit[x+i][y+j] == 0:
queue.append((x+i,y+j))
return res
最新文章
- scikit-learn 逻辑回归类库使用小结
- IIS7 IIS8 中多个版本php共存的方法
- SOA问题处理
- 低功耗蓝牙4.0BLE编程-nrf51822开发(9)
- 第一个Sprint冲刺第四天
- paypal接口对接注意事项
- IOS学习:常用第三方库(GDataXMLNode:xml解析库)
- VelocityTracker简单介绍
- 创建出多个app
- Linux内核源代码情景分析-中断半
- 样式的操作-不同浏览器加载不同的css文件
- C#导出EXCEL没有网格线的解决方法
- Java开源生鲜电商平台-搜索模块的设计与架构(源码可下载)
- 关于lnmp下 phalcon和tp框架下的nginx文件配置
- Python基础线程和协程
- 1、__del__ 2、item系列 3、__hash__ 4、__eq__
- nginx 添加虚拟主机 支持php 伪静态
- 由于没有公钥,无法验证下列签名: NO_PUBKEY 54422A4B98AB5139
- Linux学习6-CentOS搭建appium服务
- UML学习归纳整理