Сегодня в нашей задаче 2017. Grid Game требуется рассчитать оптимальную стратегию в игре с 2 участниками. И большая часть решения опять – "размышления на салфетке".
🖍️ Условие задачи
Дано: двумерный массив grid размером 2 x n, где grid[r][c] представляет количество очков в ячейке (r, c).
- Два робота начинают игру в ячейке
(0, 0) и должны достичь ячейки (1, n-1).
- Оба робота могут двигаться только вправо или вниз.
- Первый робот проходит от начальной точки до финиша, собирая все очки на своём пути.
- Затем второй робот выполняет аналогичный маршрут, при этом очки с пройденных первым роботом ячеек обнуляются.
Цель первого робота: минимизировать максимальное количество очков, которые сможет собрать второй робот.
💡 Идея
Легко увидеть, что только две стратегии второго робота могут оказаться оптимальными:
- Право → Вниз: Сначала пройти весь верхний ряд, а затем спуститься вниз на последней колонке.
- Вниз → Право: Спуститься вниз сразу, а затем двигаться вправо вдоль нижнего ряда.
Читать дальше →