Loading...
djc_bg2015 avatar 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.

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

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

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

3
djc_bg2015 avatar djc_bg2015 923 Точки

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

Поздрави!

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 4482 Точки

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

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.