[Homework] Algorithms - Recursion and Recursive Algorithms - Problem {6} - Connected Areas in a Matrix

djc_bg2015 923 Точки

[Homework] Algorithms - Recursion and Recursive Algorithms - Problem {6} - Connected Areas in a Matrix

Здравейте,

ето моето решение на задачата:

https://github.com/vdonchev/RecursionHomework/tree/master/06.ConnectedAreasInMatrix

на пръв поглед връща верни резултати.

Въпросът ми е къде греша, че немога да използвам SortedSet за записване на откритите полета?

В условието е казано:

Additionally, you can implement IComparable and store all areas found in a SortedSet.

Но, тъй като в единия пример две по две полетата са с еднакви размери , не добавя вторите резултати в хашсета и съответно накрая връща 2 намерени полета, вместо 4.

Благодаря предварително!

Тагове:

22/09/2015 14:22:55 Структури от данни и алгоритми 29/09/2015 14:24:18

ttitto 1153 Точки

Best Answer

Грешката ти е там, че сравняваш две Area само по размера им и тъй като използваш Set (т.е. не позволява duplicates) в него влиза само по една Area от всеки размер. В условието е казано още, че трябва да се сравняват и по номера на реда и след това по номера на колоната на първата клетка. Ето тук е моята имплементация на CompareTo

22/09/2015 14:34:21

djc_bg2015 923 Точки

Много благодаря, сега ще поправя кода и ще тествам.

Поздрави!

22/09/2015 14:37:26

krach 65 Точки

И аз да използвам темата ето моето решение на задачата реализирано с Java

https://github.com/krachunov/Algorithms/blob/master/src/homeWrok1/ConnectedAreas.java

25/09/2015 14:22:24

EvenOdds 7 Точки

Ето моето решение на C#:

https://github.com/VladislavNikolov/Algorithms/tree/master/Recursion-and-Recursive-Algorithms/ConnectedAreasInMatrix

Поздрави!

26/09/2015 16:59:34 26/09/2015 17:00:27

krach 65 Точки

Колега искам да попитам защо си задал MinSize = 2. Ако съм разбрал правилно, в даден лабиринт за да бъде преброен и обходен трябва да е с минимум 2 полета. Това според мен би дало проблем (няма да обходи) евентуална ареа от една клетка
___|_*_|____|____|____|
_*_|_*_|____|____|____|
___|_*_|____|____|____|
___|_*_|____|____|____|

Примерно при така подаден двумерен масив клетката 0,0 няма се се преброи.

Вярно в условието пише всички свързани клетки, но пък никъде не пише да са изрично над 2 свързани, включително.

Другото, което не е по функционалността, но за момент се обърках. В метода FindAreaStart, булевата променлива areaFound, се различава по името само с една буква от сортирания сет areasFound

26/09/2015 17:54:19

EvenOdds 7 Точки

Здравей колега,

Промених името на set-a на connectedAreasFound, за да е по-ясно какво сме намерили и да се различава от булевата променлива areaFound.
Тъй като домашните често са отворени към интерпретация реших, че една клетка не е ConnectedArea, защото не е свързана с нито една друга клетка.
Добавих и една проверка при вкарването на намерени зони в set-a, за да не се опита да създаде зона от само една клетка и да гръмне програмата.

Благодаря за коментара.

Поздрави!

26/09/2015 20:24:01

Piggov 27 Точки

Ето и моето решение - добавих и оцветяване на полетата: линк

Preview of my program

27/09/2015 19:12:53 27/09/2015 19:19:41

Filkolev 4482 Точки

Супер е. Може единствено да направиш проверка дали рандъм цвета не е същият като цвета на фона на конзолата, за да се виждат всички области (на картинката не се вижда #2).

27/09/2015 19:23:16