Сегодня в нашей задаче 2017. Grid Game требуется рассчитать оптимальную стратегию в игре с 2 участниками. И большая часть решения опять – "размышления на салфетке".
🖍️ Условие задачи
Дано: двумерный массив grid размером 2 x n, где grid[r][c] представляет количество очков в ячейке (r, c).
- Два робота начинают игру в ячейке
(0, 0) и должны достичь ячейки (1, n-1).
- Оба робота могут двигаться только вправо или вниз.
- Первый робот проходит от начальной точки до финиша, собирая все очки на своём пути.
- Затем второй робот выполняет аналогичный маршрут, при этом очки с пройденных первым роботом ячеек обнуляются.
Цель первого робота: минимизировать максимальное количество очков, которые сможет собрать второй робот.
💡 Идея
Легко увидеть, что только две стратегии второго робота могут оказаться оптимальными:
- Право → Вниз: Сначала пройти весь верхний ряд, а затем спуститься вниз на последней колонке.
- Вниз → Право: Спуститься вниз сразу, а затем двигаться вправо вдоль нижнего ряда.
А значит и первый робот должен выбрать такую колонку, чтобы минимизировать максимальное возможное количество очков для второго робота из двух вариантов.
Это задача на нахождение минимакса.
🔍 Детали подхода
-
Инициализация:
- Предварительно вычислить общее количество очков в верхнем ряду (
top_score_remained).
- Установить
bot_score_collected в 0.
-
Итерация по колонкам: Для каждой колонки выполнить моделирование процесса спуска первого робота в данной колонке
- Обновить оставшиеся очки в верхнем ряду и накопленные очки в нижнем ряду, чтобы учесть действия первого робота.
- Рассчитать максимальные очки, которые второй робот может собрать, используя одну из двух оптимальных стратегий.
- Определить минимальное значение из полученных максимумов для всех возможных разбиений маршрутов.
-
Результат:
- Вернуть минимальное значение из максимальных очков как оптимальный ход первого робота.
⏱️ Асимптотика
- Время: O(n), где
n — количество колонок. Поскольку выполняется один проход по каждой колонке, сложность линейная.
- Память: O(1), так как используются только несколько дополнительных переменных для подсчётов.
💻 Исходный код
impl Solution {
pub fn grid_game(grid: Vec<Vec<i32>>) -> i64 {
let n = grid[0].len();
// Calculate the total points in the top row initially
let mut top_score_remained: i64 = grid[0].iter().map(|&x| x as i64).sum();
let mut bot_score_collected: i64 = 0;
// Variable to track the optimal score for the second robot
let mut opt_second_score: i64 = top_score_remained;
// Iterate through each column
for j in 0..n {
// Reduce the top row points as the first robot moves
top_score_remained -= grid[0][j] as i64;
// Compute the maximum points the second robot can collect
opt_second_score = opt_second_score.min(
bot_score_collected.max(top_score_remained),
);
// Update the bottom row points collected by the first robot
bot_score_collected += grid[1][j] as i64;
}
opt_second_score
}
}