Задача на вычисление количества кратчайших путей шахматной ладьи на прямоугольной доске с обязательным посещением определенной клетки

Условие:

Код. Python

Решение:

### Предмет: Информатика, Раздел: Алгоритмы и структуры данных ### Задание: Перед нами задача на вычисление количества кратчайших путей шахматной ладьи на прямоугольной доске с обязательным посещением определенной клетки. ### Описание задачи: - Ладья должна перемещаться по доске размеров \( n \times m \) (n строк и m столбцов), начиная в верхнем левом углу (1, 1) и заканчивая в правом нижнем углу (n, m). - Обязательно нужно посетить клетку с координатами \((x, y)\) по пути. - Ладья может двигаться только вправо и вниз. ### План решения: 1. **Число путей на прямоугольной доске.** Для того чтобы посчитать количество вариантов перемещений ладьи из одной клетки в другую, можно воспользоваться динамическим программированием. Каждый шаг зависит от количества способов добраться до клетки сверху и слева. 2. **Разбиение движения на части.** - Мы должны найти количество кратчайших путей по частям: 1. Из точки \((1, 1)\) до точки \((x, y)\), 2. Из точки \((x, y)\) до точки \((n, m)\). 3. **Комбинация путей.** Всего кратчайших путей будет произведение количества путей на первом и втором участке маршрута. ### Формула для вычисления количества путей: Количество путей с движением только вправо и вниз на сетке можно найти используя биномиальные коэффициенты, или мы можем воспользоваться табличным методом динамического программирования. ### Реализация: Теперь перейдем к реализации на Python: ```python def count_ways(n, m): # Матрица для хранения количества путей до каждой клетки dp = [[0] * (m + 1) for _ in range(n + 1)] # В начальную клетку существует один путь (из неё самой) dp[1][1] = 1 # Заполняем динамическую таблицу for i in range(1, n + 1): for j in range(1, m + 1): if i == 1 and j == 1: continue dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp # Основная функция def main(): # Чтение входных данных n, m = map(int, input().split()) # Размеры доски x, y = map(int, input().split()) # Координаты обязательной клетки (x, y) # Находим количество путей из (1, 1) до (n, m) через (x, y) dp1 = count_ways(n, m) # Пути от (1, 1) до (x, y) ways_to_xy = dp1[x][y] # Пути от (x, y) до (n, m) dp2 = count_ways(n - x + 1, m - y + 1) ways_from_xy_to_nm = dp2[n - x + 1][m - y + 1] # Общее количество путей result = ways_to_xy * ways_from_xy_to_nm print(result) if __name__ == "__main__": main() ``` ### Пояснение работы программы: 1. **Функция `count_ways(n, m)`**: Она создает таблицу динамического программирования, где каждое значение в ячейке \((i, j)\) будет содержать количество способов добраться до этой клетки с позиции \((1, 1)\). Мы заполняем эту таблицу по формуле: ``` dp[i][j] = dp[i-1][j] + dp[i][j-1] ``` потому что ладья может прийти в клетку либо с левого столбца (движение вправо), либо с верхней строки (движение вниз). 2. **Основная часть программы**: - Сначала программа считывает входные данные: размеры доски и координаты обязательной клетки. - Затем с помощью динамического программирования находится количество путей до клетки \((x, y)\) и от клетки \((x, y)\) до \((n, m)\). - Умножаем количество путей на двух участках, что дает итоговое количество путей. ### Анализ сложности: - Время работы алгоритма: \(O(n \times m)\), где \(n\) — количество строк, а \(m\) — количество столбцов. Мы создаем таблицу путей и заполняем её линейно строка за строкой. - Пространственная сложность также \(O(n \times m)\), так как мы храним информацию о каждом пути в таблице. ### Пример: #### Входные данные: ``` 3 4 2 3 ``` #### Выходные данные: ``` 6 ``` И действительно, на картинке указаны 6 возможных путей для перемещения ладьи.