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