Условие задачи.
Есть шахматная доска (не классическая) размером N x N, где N = [2 ... 1000], то есть максимальный размер доски может быть 1 000 на 1 000 итого 1 000 000 (миллион) клеток. N задается в процессе работы программы. В ячейки шахматного поля раскладывают мины (на одну ячейку можно положить не больше 1ой мины). Гарантируется, что M = [0 ... (N - 2)]. Клетки, содержащие мину, будем называть запрещенными. В любую свободную клетку поля ставится КОНЬ(К). Также задается клетка, докуда ему нужно допрыгать.
Гарантируется, что:
Координаты исходной (где стоит КОНЬ) и конечной клеток НЕ совпадают
Исходная (где стоит КОНЬ) и конечная клетки свободны, то есть на них нет мин
Цель КОНЯ добраться от стартовой клетки до конечной, прыгая ТОЛЬКО на свободные клетки (без мин). То есть в ответе достаточно написать слово "Да" (если это возможно) или "Нет". Если КОНЬ после хода/прыжка окажется в клетке с миной, то ему каюк, разумеется)
===================================================================
Для наглядности приведу пример стартового поля (это лишь условный пример): chess_field.png (, : 31)
Зеленая клетка - клетка, куда стремится конь! К - стартовое положение коня. Клетки с минами (запрещенные клетки) закрашены черным фоном.
И вот эта задача на графы + BFS/DFS.
А что такое граф, в самом грубом смысле?? Граф - совокупность вершин и ребер/дуг.
Но еще есть способы задания/представления графа с точки зрения программирования/хранения в памяти! Например: матрица смежности, списки смежности, матрица инцидентности и т.д.
Шахматная доска с минами и конем НЕ является способом задания графа, как я понимаю)) Поэтому, самый важный момент на этом этапе - увязать доску с конем и графом... Именно поэтому я спрашиваю, т к, если здесь ошибиться, то все остальное будет насмарку
Как хочется соорудить граф.
1. Каждая клетка без мины (свободная клетка) шахматного поля (хотя по факту, это просто сетка на самом деле) будет выражать ВЕРШИНУ графа.
2. Кол-во вершин будущего графа считаем по формуле: N - M (кол-во всех клеток поля - кол-во запрещенных клеток). Также учитывать надо стартовую и конечную клетку.
3. Граф неориентированный, то есть конь может прыгнуть с клетки "А" в "Б" и наоборот.
4. Предельная степень любой вершины графа НЕ превосходит 8! Рисунок выше это доказывает...По факту будет гораздо меньше, ну, в среднем 2-3, наверное...
5. Нумеруем вершины графа, проходя построчно (сверху вниз) заданное шахматное поле
6. Строим списки смежности (!) - то есть формируем способ задания графа.
7. Запускаем DFS от стартовой вершины до конечной. Можно еще до запуска проверить конечную вершину по спискам смежности: если нет ни одной вершины смежной с конечной - конь стопудова не доберется до нее)
Вот пример построения списков смежности для условного примера: adj_list.png (, : 32)
Всего в графе 28 вершин. Если получать матрицу смежности, то будет нерациональное использование дин.памяти. Т к всего ячеек в такой матрице 28 * 28, а задействовано будет НЕ больше, чем 28 * 8 (в реальности в 2 раза меньше). Поэтому здесь лучше взять списки смежности. На мое ИМХО матрица смежности гораздо удобнее при кодировании, чем списки смежности, но в данном случае эта матрица смежности будет слишком разряженной...
=============================================================
Вопрос
Я правильно выбрал модель формирования графа по отношению к этой задаче? Если нет, то просьба пояснить, как можно правильнее или вообще по-другому.
Просто все дальнейшие алгоритмы завязаны именно на этой модели. Ошибка на этом этапе - ставит крест на эффективном решении данной задачи)
спс. за внимание
Добавлено
Скрытый текст
Еще вопрос вдогонку: а разве форум не поддерживает оформления в стиле LATEX, ну типа там $x^2$ или $\frac{3}{\sin(y) - 4}$, хм... думал, что какой-нибудь модуль mathjax подключен...
