Сложность: medium
Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.
Значение пути определяется минимальным числом на этом пути.
Пример:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow.
👨💻 Алгоритм:
1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.
2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.
3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.
😎 Решение:
class Solution {
let dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
func maximumMinimumPath(_ grid: [[Int]]) -> Int {
var curScore = min(grid[0][0], grid[grid.count - 1][grid[0].count - 1])
while curScore >= 0 {
if pathExists(grid, curScore) {
return curScore
} else {
curScore -= 1
}
}
return -1
}
func pathExists(_ grid: [[Int]], _ curScore: Int) -> Bool {
let R = grid.count, C = grid[0].count
var visited = Array(repeating: Array(repeating: false, count: C), count: R)
var dq: [(Int, Int)] = [(0, 0)]
visited[0][0] = true
func push(_ row: Int, _ col: Int) {
if row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore {
dq.append((row, col))
visited[row][col] = true
}
}
while !dq.isEmpty {
let (curRow, curCol) = dq.removeFirst()
if curRow == R - 1 && curCol == C - 1 {
return true
}
for dir in dirs {
push(curRow + dir[0], curCol + dir[1])
}
}
return false
}
}Ставь 👍 и забирай 📚 Базу знаний