|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 24 Nov 2001 01:43:08
To : Alexey Desyatnik
Subject : Re: Интересная задача
--------------------------------------------------------------------------------
23 Hоя 01 08:47, you wrote to all:
AD> Тут мне приспичило для олимпиады по программированию
AD> задачку придумать. Вот что на ум пришло:
AD> Дана шахматная доска NxN (8 <= N <= 10000). Далее,
AD> даны координаты коня и короля. Поставить конем шах
AD> королю за наименьшее число ходов (король не двигается).
AD> Сначала показалась довольно несложной. Hо как сел
AD> решать - ... Кроме перебора (хоть и неполного), на
AD> ум ничего не приходит. Интуиция, правда, подсказывает,
AD> что здесь алгоритм Дейкстры может быть полезен, но
AD> с какого боку - загадка... :) Может, кто уже сталкивался
AD> с такой задачкой, знает способ решения?
AD> Заранее благодарен за любую информацию
Фактически надо из одной точки перебраться в другую. Я вижу 2 варианта:
1) Все клетки - вершины графа. Дуги держать не надо, т.к. есть условие про
коня, надо только функцию от 2-х клеток, есть ход или нету, на каждую дугу надо
по 4 байта. Далее дейкстра, или волновой алгоритм
2) Hа ум пришло следующее:
A - первый массив хранит 1 клетку, где конь
/|\
B C D - второй кпримеру уже 3, куда конь может встать за 1 ход
, т.е. начало тоже, только держим на вершину по 1 бит, обнуляем все кроме той,
где конь.
- Далее берём второй массив, заполняем нулями, и в те клетки, куда может стать
конь ставим 1
- меняем массивы и повторяем предыдущий ход, при этом считаем кол-во итераций.
И там и там стожность n^3 кажется, второй вариант мы использовали когда по
памяти не проходило, а так чаще волновой или дейкстру.
Andrey
... Идея пришла в его голову и теперь упорно ищет мозг.
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
