[C#] Домашно Multidimensional Arrays - 7 Задача


2

Колеги, искам да споделя моето решение на задача 27 от книгата за C# (няма я в презентацията, но задачата е доста интересна).

Условието е: 

Напишете програма, която по подадена матрица намира най-голя-
мата област от еднакви числа. Под област разбираме съвкупност от 
съседни (по ред и колона) елементи. Ето един пример, в който имаме 
област, съставена от 13 на брой еднакви елементи със стойност 3:
 
 
Реших задачата с рекурсия. Алгоритъма се основава на две фундаментални функции: едната проверява дали текущата клетка е с валидни индекси и дали е посетена вече, другата прави рекурсията. Ако разглежданата клетка е валидна, непосетена и със стойност която ни трябва, увеличавам брояча и проверявам рекурсивно съседните клетки. 
 
Интересне ще ми е да споделите и други решения на задачата. Най-вече такива без рекурсия. Ако не сте решавали задачата, може да предложите само идея за алгоритъма.
 
ПП:
Сега видях, че да тествам алгоритъма, бях сменил първата тройка на втория ред с двойка. Затова ако пуснете кода ми резултата ще е 12.



Отговори



0

Ако искаш да я решиш без рекурсия ти препоръчвам да прочетеш какво е BFS ( Търсене в ширина ). То се имплементира с опашка ( Queue ).

https://en.wikipedia.org/wiki/Breadth-first_search

Иначе ти в момента прилагаш DFS ( Търсене в дълбочина ).


от Teodor92 (13062 точки)


0
Друг начин е да се симулира програмният стек на рекурсията, използвайки безкраен цикъл и структура от данни-стек.
Имам някъде задачка за лабиринт решена по този начин, ако искаш мога да потърся и да покажа кода. На С++ е, но точно тази част - цикли, стекове , масиви си е 1 към 1 със С#

от vdtodorov93 (754 точки)


0
Същност, ако заместиш опашката със стек в BFS, той се превръща в DFS :)

от Teodor92 (13062 точки)


3

Решението е с рекурсия, по-метода Depth-first search. Не работи за числото 0. То се явява индикатор който показва че сме посещавали дадената клетка.

От main метода правим извикване и проверяваме всеки един елемент от матрицата, който не е 0. Щом попаднем на число започваме рекурсивно търсене в четирите посоки за еднакви съседи.  За да не зациклим щом минем през някой елемент, го правим 0 и така проверяваме всички възможни бройки на съседни елементи:

http://pastebin.com/pUdNba1k

Ако някой не я е гледал – препоръчвам ви темата за Рекурсия. Алгоритъма е заимстван от задачата за търсене в лабиринт:

http://www.youtube.com/watch?v=2GCmXfKhTLc


от stanev.plamen (1143 точки)


0

Моето решение също е модификация на задачата "Пътища в лабиринт" от глава Рекурсия в учебника.

http://pastebin.com/2XkaS0ys


от dimitre_uk (0 точки)


2

Привет колеги,

Това е моето решение, може би не е много различно от посочените до момента с изключение на цветното принтиране на конзолата и това, че масивът е стрингов  но работи коректно. Приемам препоръки ;)

http://pastebin.com/UtkPw1qU




0
Това е и моето решение: http://forums.academy.telerik.com/108506/multidimensional-array-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0-7-%D0%B4%D0%BE%D0%BC%D0%B0%D1%88%D0%BD%D0%BE


0
Не съм тествал програмата реално, но... мисля че ако имаш 2 "зони" с най-често срещания елемент които не са свързани, ще оцвети всички елементи. А и от 8-те проверки си закоментирал 4, но не точно тези които трябва... трябват ти 2 проверки по хоризонтал и 2 по диагонал за да можеш да хванеш всички варианти. В текущия случай няма да хванеш зона която е свързана с друга от елемент който е съседен само по диагонал.

от JulianG (5316 точки)



0

Ето моето решение  http://pastebin.com/tav2FpLi .Реших да не използвам рекурсия този път. Използвах Stack стуктура от данни. Не съм го тествал много и доста дълги проверки съм направил, но мисля, че лесно се разбира основната идея. Приемам критики.


от N.Neikov (37 точки)


0

ето и моето решение, без рекурсия (DFS)
http://pastebin.com/P7G6FCKi




0

Аз също използвам рекурсия. За целта обхождам цялата матрица, като за всеки един елемент проверявам съседите му и ако той е със същата стойност извършвам същата проверка за неговите съседи (без за този от който съм достигнал до него) и така, докато не се открие нито един еднакъв съсед.


от Flystar (1171 точки)


0

 Може ли някой, на който му е интересно да погледне задачата, дали се чупи на някакъв тест?

http://pastebin.com/VaytygzB

Реших я съвсем самостоятелно, без да чета за breadth-in-serach или depth-in-search.

Използвах рекурсивен алгоритъм, подобен на намиране всички пътища в лабиринт. Изреждам всички квадратчета от матрицата и всяко квадратче го проверявам рекурсивно в дълбочина докъдето има равни на него елементи. Онова събиране на резултатите на 133 ред го правя, защото иначе връща равните числа само в една посока


от ivan.mihov1 (4988 точки)


0
За visited масива можеш просто да си инициализираш една bool [,] матрица, която by default ти е пълна с false стойностти, за да не я обхобдаш всеки път и си я нулираш като просто я реинициализираш. Аз бих изкарал матриците като глобални променливи както и current/max counter-ите за да не пращам на рекурсията всеки път по 10 параметъра. Избягвай да инициализираш масиви в рекурсията, защото ти го създава на всяко рекурсивко извикване. Иначе според ме нработи правилно, просто може да се направят малки оптимизации... :)


0
Аз няколко вечери и сутрини я мислих тази задача и едно утро(ето затова ходя на изпити сутрин понеже е по-мъдро от вечерта) измислих правилното решение, а именно Правим си един булев масив със същите размери като числовия. Правим си 2 променливи maxCount и currentCount. Хващаме за всяка клетка и започваме да проверяваме в 4-те посоки дали съседната клетка има същата стойност и ако да я добавяме в currentCount и извикваме същия метод за тази клетка. Когато стигнем дъното на рекурсията(клетка с различна стойност) проверяваме дали maxCount < currentCount и зануляваме последния. Като всяка клетка което сме посетили и има търсената от нас стойност й добавяме true стойност в булевия масив и ако стигнем отново до нея чрез рекурсията я прескачаме. Ако искаш мога да се поровя и да намеря кода или да го напиша наново, че това май ми е любимата задача.

от RANOPILE (1038 точки)