▲

3

▼

🚀 Игра двух роботов: вычисление минимакс стратегии для первого игрока

leetcoder, изменено 28-01-2025 , 473

Сегодня в нашей задаче 2017. Grid Game требуется рассчитать оптимальную стратегию в игре с 2 участниками. И большая часть решения опять – "размышления на салфетке".

🖍️ Условие задачи

Дано: двумерный массив grid размером 2 x n, где grid[r][c] представляет количество очков в ячейке (r, c).

• Два робота начинают игру в ячейке (0, 0) и должны достичь ячейки (1, n-1).
• Оба робота могут двигаться только вправо или вниз.
• Первый робот проходит от начальной точки до финиша, собирая все очки на своём пути.
• Затем второй робот выполняет аналогичный маршрут, при этом очки с пройденных первым роботом ячеек обнуляются.

Цель первого робота: минимизировать максимальное количество очков, которые сможет собрать второй робот.

💡 Идея

Легко увидеть, что только две стратегии второго робота могут оказаться оптимальными:

1. Право → Вниз: Сначала пройти весь верхний ряд, а затем спуститься вниз на последней колонке.
2. Вниз → Право: Спуститься вниз сразу, а затем двигаться вправо вдоль нижнего ряда.
   

А значит и первый робот должен выбрать такую колонку, чтобы минимизировать максимальное возможное количество очков для второго робота из двух вариантов.

Это задача на нахождение минимакса.

🔍 Детали подхода

1. Инициализация:
   • Предварительно вычислить общее количество очков в верхнем ряду (top_score_remained).
   • Установить bot_score_collected в 0.
2. Итерация по колонкам: Для каждой колонки выполнить моделирование процесса спуска первого робота в данной колонке
   • Обновить оставшиеся очки в верхнем ряду и накопленные очки в нижнем ряду, чтобы учесть действия первого робота.
   • Рассчитать максимальные очки, которые второй робот может собрать, используя одну из двух оптимальных стратегий.
   • Определить минимальное значение из полученных максимумов для всех возможных разбиений маршрутов.
3. Результат:
   • Вернуть минимальное значение из максимальных очков как оптимальный ход первого робота.

⏱️ Асимптотика

• Время: 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
    }
}

Tags:  #rust #algorithms #games #strategy