Задача: 1102. Path With Maximum Minimum Value
Сложность: 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 {
    vector<vector<int>> dirs{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public:
    int maximumMinimumPath(vector<vector<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;
    }

    bool pathExists(vector<vector<int>>& grid, int curScore) {
        int R = grid.size(), C = grid[0].size();
        vector<vector<bool>> visited(R, vector<bool>(C, false));
        deque<pair<int, int>> dq{{0, 0}};
        visited[0][0] = true;

        auto push = [&](int row, int col) {
            if (row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore) {
                dq.push_back({row, col});
                visited[row][col] = true;
            }
        };

        while (!dq.empty()) {
            int curRow = dq.front().first, curCol = dq.front().second;
            dq.pop_front();
            if (curRow == R - 1 && curCol == C - 1) {
                return true;
            }
            for (auto dir : dirs) {
                push(curRow + dir[0], curCol + dir[1]);
            }
        }
        return false;
    }
};

Ставь 👍 и забирай 📚 Базу знаний