Здравейте,
Има ли някой, който да е решил тази задача без "flood fill algorithm", а по някакъв друг начин?
Доста варианти мислих, но нито един не стана съвсем. Много ми е интересно просто ако някой я е решил без да използва този алгоритъм, ако иска да си сподели кода, за да го разгледам.
Камелия
Аз я реших с BFS но и с DFS става, а сигурно ако се напъне човек и с по сложните алгоритми върху графи ще стане.
Здравей,
Не мога да се сетя за различен алгоритъм - дори и за по-малко ефективен алгоритъм, които би работил. Общо взето каквото и да напишеш все ще прерасне в някаква форма на bfs/dfs (дори да е прикрито зад нещо друго), което означава, че ще е flood fill.
Едно нещо, което може би би ти било интересно, е да ползваш Point in Polygon algorithm-а - тоест да проверяваш дали всяка една клетка е в многоъгълника в матрицата, вътрешността на който оцветяваш. Но това ще работи само за случаи, когато наистина има някакъв многоъгълник, в който се намираш - за случаи като първите 2 примера за входни данни няма да работи много добре (или поне ще трябва насила да създаваш някакъв многоъгълник).
Наистина не се сещам за нещо, което би работило - ако някой колега се сети, нека каже. Но каквото и да е няма да е по-ефикасно от flood fill-а (bfs/dfs-а), защото той работи за минималното възможно време - приблизително колкото клетки има за оцветяване, толкова повторения ще се изпълнят - не би трябвало да има по-ефикасен подход от това. Но е хубаво, че се интересуваш, това е хубав подход към ученето.
Поздрави,
Жоро
Да, но тя търси друго решение - flood fill algorithm общо взето е специализиран bfs/dfs, тоест над bfs/dfs алгоритъма слагаш особеностите за конкретен "fill color" както в задачата и го правиш да счита многомерния масив за граф (алгоритъмът е общо взето същия за N-мерен масив, не е нужно да е 2D). С две думи, ако си го решил с bfs/dfs, значи си написал flood fill algorithm :)
Сега му погледнах по-подробно псевдокода. Всъщност почти същото на това което в уикипедия са го нарекли "Forest Fire algorithm" съм правил, само където ми се получи доста по-дървено, със струва ми се излишни стъпки.