@William03

Как решать задачи с таблицами (матрицами, лабиринтами) (Python)?

В олимпиадах по информатике частенько попадаются задачи, где дается матрица размером M на N (допустим) или какое-либо подобие лабиринта и необходимо найти путь из одной точки к другой, пользуясь данными в условии правилами ходов или найти наилучший путь из существующих по определенным критериям и т.д.. Это интригует, но я пока не могу понять, как решать такого рода задачи. Хотелось бы получить ответ с объяснением и несколькими примерами, рекомендациями - какие конструкции лучше использовать и какие вообще конструкции можно использовать для решения подобных задач. И ответ на такую задачу:

Лабиринт. Лабиринт задан в виде таблицы размером N×M. Стенам лабиринта соответствуют единицы, проходам — нули. Двигаться по диагонали запрещено.
Напишите программу, которая определяет длину пути L из точки с координатами (I1, J1) в точку с координатами (I2, J2). Предполагается, что если путь существует, то он единственный и не содержит петель. Если пути нет, или заданы некорректные координаты начальной и конечной точки, то L=0.
Формат входных данных:
В первой строке содержатся числа N и M (1 ≤ N, M ≤ 20) — количество строк и столбцов таблицы, задающей лабиринт.
Во второй строке записаны числа I1 и J1 — координаты начальной точки.
В третьей строке записаны числа I2 и J2 — координаты конечной точки.
В следующих N строках задаются элементы таблицы, разделенные пробелом.
Формат выходных данных:
Длина пути L из точки с координатами (I1, J1) в точку с координатами (I2, J2).
Пример № 1:
Input:
4 5
4 1
1 4
1 1 0 0 1
0 0 1 0 1
1 0 0 0 0
0 0 1 0 0
Output:
7
Пример № 2:
Input:
4 5
1 1
1 4
1 1 0 0 1
0 0 1 0 1
1 0 0 0 0
0 0 1 0 0
Output:
0
Пример № 3:
Input:
4 5
2 1
2 1
1 1 0 0 1
0 0 1 0 1
1 0 0 0 0
0 0 1 0 0
Output:
1
  • Вопрос задан
  • 788 просмотров
Решения вопроса 1
@xdgadd
ML/Python/Cpp
Это задачи на графы.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Astrohas
@Astrohas
Python/Django Developer
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы