dufifa: Тут простейшая геометрия и Google Maps JavaScript API
jQuery в этой задаче тебе и не нужен, если откроешь доку там есть примеры
Там же есть дополнительная либа по геометрии, то что тебе и нужно
https://developers.google.com/maps/document...script/geometry

https://forum.sources.ru/index.php?showtopic=421242&view=findpost&p=3845548

swf: Замечу только, что всех путей в ациклическом орграфе может быть экспоненциальное количество от числа вершин.
Будет ли работать раскраска, ещё не поняла. Щас подумаю :)

Добавлено 18.03.21, 20:32
С раскраской всё правильно.
Всегда ли мы можем раскрасить вершины? Когда мы не можем покрасить. Если из непокрашенной вершины v есть путь в непокрашенную вершину u. А из непокрашенной u есть путь в непокрашенную v. Чтобы покрасить вершину v, надо знать цвета всех следующих, то есть надо знать и цвет u. А чтобы узнать цвет u, нужно знать цвета всех следующих, в том числе и v.
Но в этом случае между u и v замыкается орцикл, которого быть не должно.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845546

Vesper:
Неправильно доказывал, значит. Потому как та же вики гласит, что кривая Пеано как функция не является инъективной, то есть существуют элементы образа, не имеющие прообраза.

https://forum.sources.ru/index.php?showtopic=381032&view=findpost&p=3845545

AVA12: Я категорически отказываюсь понимать, что происходит.

amk и я предлагаем простой, надежный, независящий от порядка обхода алгоритм из двух простейших правил. FasterHarder каким-то образом усматривает в нем изъяны и в качестве "иллюстрации" выдает совершенно другой, непонятно откуда взявшийся и явно кривой алгоритм. Время от времени Akina и OpenGL предлагают свои варианты алгоритмов.

В связи с чем вопрос: а о чем конкретно мы беседуем?

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845544

Сергей85:
У меня проблема уже решена. Вы кому отвечаете?

https://forum.sources.ru/index.php?showtopic=419400&view=findpost&p=3845543

prografix: applegame
Спасибо за ссылку. Я тоже попробовал. Хорошо, но не идеально. Пусть ещё поработают.

https://forum.sources.ru/index.php?showtopic=363203&view=findpost&p=3845542

OpenGL:
Если решать обходом в ширину, а не в глубину, то действительно немного сложнее получается. Но, если поменять порядок раскраски и помещения в очередь, то обходом в ширину тоже несложно выходит

1. Кладём все тупики в очередь (только кладём, не раскрашиваем)
2. Если очередь пуста - выходим. Иначе - п.3.
3. Достаём из очереди очередную вершину. Если она покрашена, то её просто пропускаем и идём в п.2. Иначе - п.4
4. Смотрим на список вершин, в которые мы можем из текущей вершины попасть. Есть три возможных варианта
   
   • Есть вершины, в которые мы можем попасть из текущей и которые мы ещё не покрасили. В этом случае просто эту вершину пропускаем, вернёмся к ней позже.
   • Есть вершины, которые мы покрасили в красный. Тогда текущую красим в зелёный
   • В списке красных вершин нет. Тогда в красный цвет красим текущую (в частности, у тупиков красных вершин не будет, поэтому они покрасятся в красный).
   Если выполнился вариант 2 или 3 (т.е. если мы покрасили вершину), то идём в п.5, иначе в п.2
5. Все вершины, из которых мы можем попасть в текущую, закидываем в очередь, и идём в п. 2

Насчёт подпунктов пункта 4. Может быть такое, что у тебя одновременно выполняются первые два пункта (покрашены не все вершины, и среди покрашенных есть красные), в этом случае можешь любое действие выполнять, на результат это не повлияет.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845540

kiddan: Разобрался, всем спасибо кто помог!!!

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845539

FasterHarder:
нет, конечно)

цель каждого игрока - сходить в КРАСНУЮ вершину, чтобы у противника не было хода, т е загнать противника в тупик


она верная, если следовать озвученным правилам. проблема в правилах



скорее всего в этих словах есть смысл и надо копать в этом направлении) но это сложно!)
ведь с ракраской так все просто казалось, а получать все пути - это же жесть как геморрно..Может попроще что-то есть)

Добавлено 18.03.21, 06:23
в общем ладно, пока уберу анализ в не самый далекий ящик. Тут надо исследовать все с самого начала и думать с нуля.
пока решение не идет, значит, надо подождать, как говорит Макконел))

РЕЗЮМЕ: не смог я решить!! ну ладно) авось решу еще, но это неточно...Хотя код я уже давно накропал и мне казалось все там прекрасно, но прожка из 200 тестов 7 тестов НЕ проходит. и так сойдет ))

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845537

Akina:
С чего бы? ход первого игрока на красный узел - это проигрыш.

И раскраска на рисунке неверная. Я ещё давно говорил, что начинать надо с поиска всех путей. Потому что раскраска должна вестись строго с учётом чётности пути. Тупик на пути чётной длины - красный, на пути нечётной длины - зелёный, если в узел ведёт несколько путей, то узел зелёный лишь в случае, когда он зелёный для всех путей, не имеющих ветвлений на нечётных узлах.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845536

FasterHarder:
это, очевидно, что ложь
________________.png (, : 81)
----------------------------------------------------
в итоге, еще подумав над раскраской начал осознавать, что здесь все гораздо и гораздо и гораздо сложнее, это я за себя говорю)) + сформулировать правила раскраски - проблемно...

ласт попытка сделать некие правила, хотя ни в одном из них я уже не уверен:
1. все тупики красные по дефалту и они являются эпицентрами начала движения по вершинам орграфа (дуги инвентированы)
2. зеленую порождает красная
3. красную порождает зеленая
4. красная вершина должна иметь только зеленых соседей. ИСКЛЮЧЕНИЕ: если есть хотя бы один красный сосед, то у этого красного соседа в свою очередь все соседи должны быть красными. Но это невозможно, чтобы у красного все соседи были красными), поэтому, красная вершина должна иметь ТОЛЬКО зеленых соседей - я не уверен в этом на 100%, не знаю...
5. зеленая вершина должна иметь хотя бы одного красного соседа (ИСКЛЮЧЕНИЕ: если все соседи зеленые, то у любого из этих зеленых соседей тоже все соседи должны быть зелеными, но это вроде тоже невозможно - не уверен на 100%, не знаю...)
не уверен, но вроде в п4 и п5 исключения можно отбросить. не знаю
и т.д.

ну и главная проблема - порядок обхода вершин, хотя это не должно влиять, а по факту влияет. Картинка чуть выше. Если сделать обход чуть по-другому, то вершина №1 станет красной и это уже будет правильно.

зы: уже нет абсолютно никакой уверенности, что задачу эту можно решить именно подобной раскраской и ведь выше было замечено, что здесь полный перебор (класс NP), хотя я не уверен, что я правильно понял про какой перебор там идет речь - слишком поверхностно все было написано. 1ая мысль, которая пришла в ум - был полный перебор - не удивлюсь, что в конечном итоге все к нему и сведется, т к раскраской эта задача НЕ решается))

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845535

Akina: Насколько велика таблица joomla_content? Если её задампить и зипануть - приложится к сообщению? чтобы на реальных данных тестировать, а не гадать на кофейной гуще..

https://forum.sources.ru/index.php?showtopic=419400&view=findpost&p=3845534

^D^ima: kiddan
Код то покажи, мы не умеем гадать

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845528

Сергей85: В тегах у меня есть пробелы, но не в названиях разделов.

https://forum.sources.ru/index.php?showtopic=419400&view=findpost&p=3845526

Akina:
Символы, которые не видны при обычном отображении. Например, пробел на конце строки - поди его увидь... Или, скажем, символ, изображение которого в текущем шрифте имеет нулевую ширину. Да мало ли...

https://forum.sources.ru/index.php?showtopic=419400&view=findpost&p=3845525

Сергей85:
Что такое скрытые символы?

https://forum.sources.ru/index.php?showtopic=419400&view=findpost&p=3845524

AVA12:
Блин, FasterHarder, да прочитай ты уже написанное!

Тут очевидно, что если из некоторой вершины есть ребро, ведущее в зеленую, то сама эта вершина должна быть красной, и никакие подходы, никакие кривые пути этот факт не изменят. Вершина, покрашенная в красный, красной и останется.

Тут очевидно, что прежде чем покрасить вершину в зеленый, нужно покрасить все смежные с ней, а тогда ее цвет определяется однозначно и не меняется. Вершина, покрашенная в зеленый, зеленой и останется.

Здесь выбор порядка обхода вершин ни на что не влияет. Можно обходить вершины в случайном порядке - если применять только эти два правила, результат в любом случае будет один и тот же! Ты же перемудрил и взял откуда-то совершенно левый навороченный алгоритм, который не равнозначен этим двум простым правилам.


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

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845523

kiddan: Странно в ListBox отрабатывает,а при writeln(f,subs); в файле только последние 5 символов!

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845519

^D^ima: Как ещё вариант:

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845510

kiddan: Спасибо за помощь!!! Дай Вам Бог здоровья!!!!

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845509