1102. Path With Maximum Minimum Value
Дана целочисленная матрица 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.
C# решение
сопоставлено/оригиналpublic class Solution {
private static readonly int[][] dirs = new int[][] {
new int[] {1, 0}, new int[] {0, 1}, new int[] {-1, 0}, new int[] {0, -1}
};
public int MaximumMinimumPath(int[][] grid) {
int R = grid.Length, C = grid[0].Length;
int curScore = Math.Min(grid[0][0], grid[R - 1][C - 1]);
while (curScore >= 0) {
if (PathExists(grid, curScore)) {
return curScore;
} else {
curScore--;
}
}
return -1;
}
private bool PathExists(int[][] grid, int curScore) {
int R = grid.Length, C = grid[0].Length;
bool[][] visited = new bool[R][];
for (int i = 0; i < R; i++) {
visited[i] = new bool[C];
}
Queue<(int, int)> dq = new Queue<(int, int)>();
dq.Enqueue((0, 0));
visited[0][0] = true;
while (dq.Count > 0) {
(int curRow, int curCol) = dq.Dequeue();
if (curRow == R - 1 && curCol == C - 1) {
return true;
}
foreach (var dir in dirs) {
int newRow = curRow + dir[0], newCol = curCol + dir[1];
if (newRow >= 0 && newCol >= 0 && newRow < R && newCol < C && !visited[newRow][newCol] && grid[newRow][newCol] >= curScore) {
dq.Enqueue((newRow, newCol));
visited[newRow][newCol] = true;
}
}
}
return false;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private static readonly int[][] dirs = new int[][] {
new int[] {1, 0}, new int[] {0, 1}, new int[] {-1, 0}, new int[] {0, -1}
};
public int MaximumMinimumPath(int[][] grid) {
int R = grid.size(), C = grid[0].size();
int curScore = min(grid[0][0], grid[R - 1][C - 1]);
while (curScore >= 0) {
if (PathExists(grid, curScore)) {
return curScore;
} else {
curScore--;
}
}
return -1;
}
private bool PathExists(int[][] grid, int curScore) {
int R = grid.size(), C = grid[0].size();
bool[][] visited = new bool[R][];
for (int i = 0; i < R; i++) {
visited[i] = new bool[C];
}
queue<(int, int)> dq = new queue<(int, int)>();
dq.Enqueue((0, 0));
visited[0][0] = true;
while (dq.size() > 0) {
(int curRow, int curCol) = dq.Dequeue();
if (curRow == R - 1 && curCol == C - 1) {
return true;
}
foreach (var dir in dirs) {
int newRow = curRow + dir[0], newCol = curCol + dir[1];
if (newRow >= 0 && newCol >= 0 && newRow < R && newCol < C && !visited[newRow][newCol] && grid[newRow][newCol] >= curScore) {
dq.Enqueue((newRow, newCol));
visited[newRow][newCol] = true;
}
}
}
return false;
}
}Java решение
auto-draft, проверить перед отправкойimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
private static readonly int[][] dirs = new int[][] {
new int[] {1, 0}, new int[] {0, 1}, new int[] {-1, 0}, new int[] {0, -1}
};
public int MaximumMinimumPath(int[][] grid) {
int R = grid.length, C = grid[0].length;
int curScore = Math.min(grid[0][0], grid[R - 1][C - 1]);
while (curScore >= 0) {
if (PathExists(grid, curScore)) {
return curScore;
} else {
curScore--;
}
}
return -1;
}
private boolean PathExists(int[][] grid, int curScore) {
int R = grid.length, C = grid[0].length;
boolean[][] visited = new boolean[R][];
for (int i = 0; i < R; i++) {
visited[i] = new boolean[C];
}
Queue<(int, int)> dq = new LinkedList<(int, int)>();
dq.Enqueue((0, 0));
visited[0][0] = true;
while (dq.size() > 0) {
(int curRow, int curCol) = dq.poll();
if (curRow == R - 1 && curCol == C - 1) {
return true;
}
foreach (var dir in dirs) {
int newRow = curRow + dir[0], newCol = curCol + dir[1];
if (newRow >= 0 && newCol >= 0 && newRow < R && newCol < C && !visited[newRow][newCol] && grid[newRow][newCol] >= curScore) {
dq.Enqueue((newRow, newCol));
visited[newRow][newCol] = true;
}
}
}
return false;
}
}JavaScript решение
сопоставлено/оригиналvar maximumMinimumPath = function(grid) {
const R = grid.length, C = grid[0].length
let curScore = Math.min(grid[0][0], grid[R - 1][C - 1])
while (curScore >= 0) {
if (pathExists(grid, curScore)) {
return curScore
}
curScore--
}
return -1
}
var pathExists = function(grid, curScore) {
const R = grid.length, C = grid[0].length
const visited = Array.from({ length: R }, () => Array(C).fill(false))
const dq = [[0, 0]]
visited[0][0] = true
const push = (row, col) => {
if (row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore) {
dq.push([row, col])
visited[row][col] = true
}
}
while (dq.length > 0) {
const [curRow, curCol] = dq.shift()
if (curRow == R - 1 && curCol == C - 1) {
return true
}
push(curRow + 1, curCol)
push(curRow - 1, curCol)
push(curRow, curCol + 1)
push(curRow, curCol - 1)
}
return false
}Python решение
сопоставлено/оригиналfrom collections import deque
class Solution:
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
def pathExists(curScore):
R, C = len(grid), len(grid[0])
visited = [[False] * C for _ in range(R)]
dq = deque([(0, 0)])
visited[0][0] = True
def push(row, col):
if 0 <= row < R and 0 <= col < C and not visited[row][col] and grid[row][col] >= curScore:
dq.append((row, col))
visited[row][col] = True
while dq:
curRow, curCol = dq.popleft()
if curRow == R - 1 and curCol == C - 1:
return True
for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
push(curRow + dr, curCol + dc)
return False
curScore = min(grid[0][0], grid[-1][-1])
while curScore >= 0:
if pathExists(curScore):
return curScore
curScore -= 1
return -1Go решение
сопоставлено/оригиналtype cell struct {
row, col int
}
var dirs = [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
func maximumMinimumPath(grid [][]int) int {
R, C := len(grid), len(grid[0])
curScore := min(grid[0][0], grid[R-1][C-1])
for curScore >= 0 {
if pathExists(grid, curScore) {
return curScore
}
curScore--
}
return -1
}
func pathExists(grid [][]int, curScore int) bool {
R, C := len(grid), len(grid[0])
visited := make([][]bool, R)
for i := range visited {
visited[i] = make([]bool, C)
}
dq := []cell{{0, 0}}
visited[0][0] = true
push := func(row, col int) {
if row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore {
dq = append(dq, cell{row, col})
visited[row][col] = true
}
}
for len(dq) > 0 {
curCell := dq[0]
dq = dq[1:]
if curCell.row == R-1 && curCell.col == C-1 {
return true
}
for _, dir := range dirs {
push(curCell.row+dir[0], curCell.col+dir[1])
}
}
return false
}
func min(a, b int) int {
if a < b {
return a
}
return b
}Algorithm
Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.
Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.
Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.