Софтуерно Инженерство
Loading...
+ Нов въпрос
djc_bg2015 avatar djc_bg2015 922 Точки

[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.

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

Тагове:
3
Структури от данни и алгоритми 29/09/2015 14:24:18
ttitto avatar ttitto 1155 Точки
Best Answer

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

3
djc_bg2015 avatar djc_bg2015 922 Точки

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

Поздрави!

1
krach avatar krach 65 Точки

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

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

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


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

2
EvenOdds avatar EvenOdds 7 Точки

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

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

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

Поздрави!

3
Piggov avatar Piggov 27 Точки

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

Preview of my program

3
27/09/2015 19:19:41
Filkolev avatar Filkolev 4501 Точки

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

1