|
Задачка про остров
|
|||
---|---|---|---|
#18+
Кто захочет поразвлекаться, исходные данные в массиве, списком и графом Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49.
Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 01:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
автори вот опять же, как быстро считать площади дырок на каждом срезе. Когда у тебя есть массив луж, посчитать мне кажется сравнительно легко. Перебираешь высоты всех хексов, которые лужу окружают, берешь высоту самого маленького (Скажем X). V воды в луже единичного хекса = (X-высота этого хекса)*1 //*1 потому как площадь хекса равна условной единице. Повторить для всех хексов которые в этой луже (т.е. исключить подсписок, который будет после рекурсии - т.е. исключить вложенную лужу, бортики этой лужи сами исключатся, потому что они выше X). ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 02:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Задачу можно решать по разному. Можно - как олимпиадную - такими деревянными матрциами и хардкодом топологии. Давайте ее сведем хотя-бы к уровню постнаовки и решения на теории графов. Есть моё предположение что детектирование мостов и связности упрощает эту задачу. Опять-же для некого подмножества исходных данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 10:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, я их всего этого набора слов гед-то слышал только матрица и графы :) Разверни свой вариант. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 11:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9.
Я согласен помогать и задачки на графы - интересны но мне часто лень тратить своё время на пустяки. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 11:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я тоже в сторонке постою, мне не то что лень, но с этими фокусами я мало знаком, а учить ради единоразового представления пятисотую по счету технологию, это только за деньги на работе. Хотя что эт отакое посмотрю конечно, интересно же. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:03 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. Я вообще хотел поднять отдельный топик. В продолжение моих Java Graph Libraries поисковых вопросов. Primary Goal : на посмотреть параллельные алгоритмы на графах (к сожалению еще не выбрал какие). Secondary Goal : java, atomic, locks, не-блокирующие коллекции и структуры данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz Объекты Hexagon - ноды графа, каждая нода связана с другими (грань связана с другой нодой или null), для реализации алгоритма на жаве самое то. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:26 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev mayton Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz Объекты Hexagon - ноды графа, каждая нода связана с другими (грань связана с другой нодой или null), для реализации алгоритма на жаве самое то. Я согласен но я говорю про обобщенные алгоритмы которые могут работать не для хексагонов а для плиток любой геометрии. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хм. А оказалось ничего сложного осваивать не надо, осталось понять как каждой ноде вес присвоить. http://www.webgraphviz.com Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:55 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Подправил 41 и 42ую связи "de"->"ce" "ca"->"da" Блин вот красивая картинка. digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" } ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
нули точно нужны? вся картинка слетит - будет почти от каждого узла в ноль стрелка ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, я не вижу картинок с хостинга https://d.radikal.ru/ Пожалуйста перепость их куда-то в другое место. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:09 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Сами напросились нуль добавлен. digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" "aa"->"null" "ab"->"null" "ac"->"null" "ba"->"null" "bd"->"null" "ca"->"null" "ce"->"null" "da"->"null" "de"->"null" "ea"->"null" "eb"->"null" "ec"->"null" } https://jpegshare.net/][img=https://jpegshare.net/images/86/d0/86d03158ddfb4e11defdb7c989bae08c.jpg[/img] ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
[quot АСУ ТПшник#22077547]Сами напросились нуль добавлен. digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" "aa"->"null" "ab"->"null" "ac"->"null" "ba"->"null" "bd"->"null" "ca"->"null" "ce"->"null" "da"->"null" "de"->"null" "ea"->"null" "eb"->"null" "ec"->"null" } посоветуйте такой жу удобный как радикал картинкохранилище без регистраций и прочего... https://jpegshare.net/86/d0/86d03158ddfb4e11defdb7c989bae08c.jpg.html ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Увы увы. Либо амазон либо гуглдрайв. Последник шарится через веб или нет я не помню. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Я согласен но я говорю про обобщенные алгоритмы которые могут работать не для хексагонов а для плиток любой геометрии. Не любые плитки могут сложиться также как шестигранники, да и проблем особых нет, я забил константой количество граней, но можно сделать инициализацию массива граней на требуемую размерность и работай себе с любым количеством граней. Другой вопрос в каком формате загонять тестовые данные, для простого примера с обычного плоского массива (который ты сам и предложил))) высот самый оптимальный вариант, сложный пример желательно в чем то рисовать, скидывать в файл и засасывать файл в свою структуру для обсчета. В рисовалках подобных вещей не силен, тем более в их сопряжении с жавой, вообще жавист у нас ты один)) PS: у нас пока вменяемого алгоритма нет даже для шестигранников. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, Ориентация дуг графа у тебя неправильная, каждая дуга будет иметь направление от более высокой плитки к более низкой (путь по которому сливается вода с более высокой плитки), если смотреть со стороны нод то вес дуги для нод к примеру 3 и 9 будет для тройки 6 для девятки -6. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Поэтому слезно прошу - посмотрите на мой вариант. Алгоритм один послойный. Тупой как пробка. Самое сложное - найти таки эти окружности, что опять же решается в двумерном пространстве. На каждую лужу - заряжаем опять ровно этот же алгоритм в рекурсии, пока не дойдем до вариант - что луж в остатке нет. Я же не просто так написал, закрашивание оно игтуитивно понятно было с самого начала. Ты совершенно прав, идти нужно сверху, также как идет вода при отливе с каждой ступенькой оставляя либо залитые либо сухие плитки. Задача на самом деле несколько сложнее чем показалась сначала, для тестирования нужны случаи, когда есть как минимум три концентрические секции океан - стена - ров - стена - ров - ... - стена - центральное озеро и возможно сухой выступ в середине озера, ведь в каждой луже могут быть выступающие над уровнем незалитые водой плитки. Две концентрические системы должны быть связаны разными кольцами на разном уровне (сообщающиеся сосуды), чтобы вода перетекала из одной системы в другую и глубина заполнения одного из рвов определялась соседней системой, рвы могут быть незамкнутыми кольцами, третья концентрическая система должна быть независимой. В общем задача найти все сухие и все залитые плитки совсем не тривиальная. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторТы совершенно прав, идти нужно сверху, также как идет вода при отливе с каждой ступенькой оставляя либо залитые либо сухие плитки. Задача на самом деле несколько сложнее чем показалась сначала, для тестирования нужны случаи, когда есть как минимум три концентрические секции океан - стена - ров - стена - ров - ... - стена - центральное озеро и возможно сухой выступ в середине озера, ведь в каждой луже могут быть выступающие над уровнем незалитые водой плитки. Две концентрические системы должны быть связаны разными кольцами на разном уровне (сообщающиеся сосуды), чтобы вода перетекала из одной системы в другую и глубина заполнения одного из рвов определялась соседней системой, рвы могут быть незамкнутыми кольцами, третья концентрическая система должна быть независимой. В общем задача найти все сухие и все залитые плитки совсем не тривиальная. Да все это учтено в моем алгоритме. Посчитать количество воды в луже любой конфигурации не трудно, как только ты знаешь, что внутри лужи другой лужи нет - бублика. Основная сложность найти главные лужи, вот это я и предложил за один проход высчитать. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторОриентация дуг графа у тебя неправильная, каждая дуга будет иметь направление от более высокой плитки к более низкой Это не ставилось целью мной какбы. Вот вам исходник, делайте что хотите. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:55 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Да все это учтено в моем алгоритме. Посчитать количество воды в луже любой конфигурации не трудно, как только ты знаешь, что внутри лужи другой лужи нет - бублика. Основная сложность найти главные лужи, вот это я и предложил за один проход высчитать. Количество воды не интересно. Вложенных бубликов может быть сколько угодно, ров это тоже лужа, внутри луж могут быть выступы, поэтому я и говорю, задача найти все сухие и все затопленные плитки весьма нетривиальная. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Это не ставилось целью мной какбы. Вот вам исходник, делайте что хотите. Исходник для расчета я сделал немного выше, шестисвязный список Hexagon, к нему можно итератор приделать, чтобы можно было переходить с ноды на ноду, посмотреть высоту ноды и высоты соседних уже можно сейчас, дело только за алгоритмом, которого пока нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хммм... Еще раз подумайте над моим алгоритмом, все учтено. И сосуды и прочее. Режем по слоям - где нет замкнутой фигуры - вода польется куда то еще. Ров уровня 0 - будет резать люой бублик и в него уходить будет вода. Кляксу в кляке нарисуйте, соедините их рвом, алгоритм все равно сжует это и не поперхнется - бублики будут рисоваться на срезе рва (т.е. самой низкой точки берега рва)). Если их нет замкнутых - ваша вода утекла в море. Чего уже проще - если фигура замкнута, никуда ничего из нее не потечет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:02 |
|
|
start [/forum/topic.php?fid=16&msg=39925182&tid=1339799]: |
0ms |
get settings: |
8ms |
get forum list: |
11ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
281ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
others: | 15ms |
total: | 392ms |
0 / 0 |