广度优先遍历解题的代码,以及踩的一个坑
来源:9-4 LeetCode:417. 太平洋大西洋水流问题

weixin_慕的地2310058
2020-07-26
想问一下老师,从海岸线向内陆遍历,而不是从内陆的每个点向海岸线遍历,是考虑节约时间吗? 因为一开始的思路就是从陆地上每个点开始遍历。
从海岸线向内陆进行广度优先遍历,代码如下:
var pacificAtlantic = function(matrix) {
if (matrix.length === 0) return []
const n = matrix.length, // 行数
m = matrix[0].length // 列数
const matrix1 = Array.from({length: n}, () => new Array(m).fill(false)) // 记录能否流入太平洋
const matrix2 = Array.from({length: n}, () => new Array(m).fill(false)) // 记录能否流入大西洋
const borders1 = [], borders2 = [] // 太平洋、大西洋的海岸 的坐标
for (let i = 0; i < m; i ++) {borders1.push([0, i])}
for (let i = 1; i < n; i ++) {borders1.push([i, 0])}
for (let i = 0; i < m; i ++) {borders2.push([n - 1, i])}
for (let i = 0; i < n - 1; i ++) {borders2.push([i, m - 1])}
// 广度优先遍历
borders1.forEach(point => {
let queue = [point]
let visited = new Set()
visited.add(point.toString())
while (queue.length > 0) {
[x, y] = queue.shift()
matrix1[x][y] = true
let neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
neighbors.forEach(neighbor => {
[x1, y1] = neighbor
if (!visited.has([x1, y1].toString()) && x1 <= n - 1 && x1 >= 0 && y1 <= m -1 && y1 >= 0 && matrix[x1][y1] >= matrix[x][y]) {
queue.push([x1, y1])
visited.add([x1, y1].toString())
}
})
}
})
borders2.forEach(point => {
let queue = [point]
let visited = new Set()
visited.add(point.toString())
while (queue.length > 0) {
[x, y] = queue.shift()
matrix2[x][y] = true
let neighbors = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
neighbors.forEach(neighbor => {
[x1, y1] = neighbor
if (!visited.has([x1, y1].toString()) && x1 <= n - 1 && x1 >= 0 && y1 <= m -1 && y1 >= 0 && matrix[x1][y1] >= matrix[x][y]) {
queue.push([x1, y1])
visited.add([x1, y1].toString())
}
})
}
})
const res = []
for (let x = 0; x < n; x++) {
for (let y = 0; y < m; y++) {
if (matrix1[x][y] && matrix2[x][y]) res.push([x, y])
}
}
return res
};
踩坑:
建立新矩阵的时候
const m = new Array(5).fill(new Array(5).fill(false))
这样的话,m中每一个元素都是同一个数组,地址相同,
进行操作后:
m[0][0] = true
m 矩阵就变成了:
[
[ true, false, false, false, false ],
[ true, false, false, false, false ],
[ true, false, false, false, false ],
[ true, false, false, false, false ],
[ true, false, false, false, false ]
]
写回答
1回答
-
lewis
2020-07-26
从海岸线逆流而上确实效率更高。因为从内陆进行搜索的话,需要试验的地点太多了。
10
相似问题