Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846154 Fri, 09 Apr 2021 19:41:58 +0000 Конь прыгает по шахматной доске с минами https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846154
Добавлено
Граф не нужен. Бинарная матрица.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846081 Thu, 08 Apr 2021 14:44:03 +0000 Конь прыгает по шахматной доске с минами https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846081 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846080 Thu, 08 Apr 2021 14:39:18 +0000 Конь прыгает по шахматной доске с минами https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846080 OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846075 Thu, 08 Apr 2021 06:03:18 +0000 Конь прыгает по шахматной доске с минами https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846075 Цитата FasterHarder @
матрица смежности гораздо удобнее при кодировании

Крайне спорное утверждение, если данные хранятся в программе. Просто список смежности делается двухуровневым - разреженный (а при сплошной, а не координатной, нумерации, как на скрине - вообще обычный) вектор вершин (указатели на элементы списка смежности, он же список непосредственной достижимости) и собственно список.

Или, если в языке имеется - то ассоциативный массив (коллекция), где ключ - номер вершины, а значение - вектор достижимых вершин.

Вот если они лежат в БД - то да.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846072 Thu, 08 Apr 2021 00:08:40 +0000 Конь прыгает по шахматной доске с минами https://forum.sources.ru/index.php?showtopic=421322&view=findpost&p=3846072
Условие задачи.
Есть шахматная доска (не классическая) размером N x N, где N = [2 ... 1000], то есть максимальный размер доски может быть 1 000 на 1 000 итого 1 000 000 (миллион) клеток. N задается в процессе работы программы. В ячейки шахматного поля раскладывают мины (на одну ячейку можно положить не больше 1ой мины). Гарантируется, что M = [0 ... (N - 2)]. Клетки, содержащие мину, будем называть запрещенными. В любую свободную клетку поля ставится КОНЬ(К). Также задается клетка, докуда ему нужно допрыгать.
Гарантируется, что:
  • Координаты исходной (где стоит КОНЬ) и конечной клеток НЕ совпадают
  • Исходная (где стоит КОНЬ) и конечная клетки свободны, то есть на них нет мин

Цель КОНЯ добраться от стартовой клетки до конечной, прыгая ТОЛЬКО на свободные клетки (без мин). То есть в ответе достаточно написать слово "Да" (если это возможно) или "Нет". Если КОНЬ после хода/прыжка окажется в клетке с миной, то ему каюк, разумеется)
===================================================================
Для наглядности приведу пример стартового поля (это лишь условный пример):
chess_field.png (, : 69)
Зеленая клетка - клетка, куда стремится конь! К - стартовое положение коня. Клетки с минами (запрещенные клетки) закрашены черным фоном.
И вот эта задача на графы + BFS/DFS.

А что такое граф, в самом грубом смысле?? Граф - совокупность вершин и ребер/дуг.
Но еще есть способы задания/представления графа с точки зрения программирования/хранения в памяти! Например: матрица смежности, списки смежности, матрица инцидентности и т.д.
Шахматная доска с минами и конем НЕ является способом задания графа, как я понимаю)) Поэтому, самый важный момент на этом этапе - увязать доску с конем и графом... Именно поэтому я спрашиваю, т к, если здесь ошибиться, то все остальное будет насмарку

Кстати, напомню возможные ходы шахматного коня:
horse_moves.png (, : 422)

Как хочется соорудить граф.
1. Каждая клетка без мины (свободная клетка) шахматного поля (хотя по факту, это просто сетка на самом деле) будет выражать ВЕРШИНУ графа.
2. Кол-во вершин будущего графа считаем по формуле: N - M (кол-во всех клеток поля - кол-во запрещенных клеток). Также учитывать надо стартовую и конечную клетку.
3. Граф неориентированный, то есть конь может прыгнуть с клетки "А" в "Б" и наоборот.
4. Предельная степень любой вершины графа НЕ превосходит 8! Рисунок выше это доказывает...По факту будет гораздо меньше, ну, в среднем 2-3, наверное...
5. Нумеруем вершины графа, проходя построчно (сверху вниз) заданное шахматное поле
6. Строим списки смежности (!) - то есть формируем способ задания графа.
7. Запускаем DFS от стартовой вершины до конечной. Можно еще до запуска проверить конечную вершину по спискам смежности: если нет ни одной вершины смежной с конечной - конь стопудова не доберется до нее)

Вот пример построения списков смежности для условного примера:
adj_list.png (, : 450)

Всего в графе 28 вершин. Если получать матрицу смежности, то будет нерациональное использование дин.памяти. Т к всего ячеек в такой матрице 28 * 28, а задействовано будет НЕ больше, чем 28 * 8 (в реальности в 2 раза меньше). Поэтому здесь лучше взять списки смежности. На мое ИМХО матрица смежности гораздо удобнее при кодировании, чем списки смежности, но в данном случае эта матрица смежности будет слишком разряженной...
=============================================================

Вопрос
Я правильно выбрал модель формирования графа по отношению к этой задаче? Если нет, то просьба пояснить, как можно правильнее или вообще по-другому.
Просто все дальнейшие алгоритмы завязаны именно на этой модели. Ошибка на этом этапе - ставит крест на эффективном решении данной задачи)

спс. за внимание

Добавлено
Скрытый текст
Еще вопрос вдогонку: а разве форум не поддерживает оформления в стиле LATEX, ну типа там $x^2$ или $\frac{3}{\sin(y) - 4}$, хм... думал, что какой-нибудь модуль mathjax подключен...
]]> FasterHarder Алгоритмы