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


6

Условие: * Write a program that finds the largest area of equal neighbor elements in a rectangular matrix and prints its size.

1 3 2 2 2 4
3 3 3 2 4 4
4 3 1 2 3 3
4 3 1 3 3 1
4 3 3 3 1 1

 

Решениеsource.

Обяснение: Правим стандартно търсене в дълбочина (DFS) от всяка клетка, която не е обходена вече. На всяко търсене броим съседните клетки и намираме максималната сума.

 




Отговори



1

от zlatkov (580 точки)


0
добро решение, само искам да отбележа, че вместо да сравняваш bool_expression == false, може да използваш !bool_expression - просто да отречеш израза ;)



5
Здравейте! Ето и моето решение на задачата.
http://pastebin.com/rU6Zr4Uk
По обща идея то е подобно на горните - първо въвеждам елементите на матрицата, след което започвам обхождането им един по един като обхождането на един елемент включва рекурсивния метод SearchPath. SearchPath всъщност маркира текущия елемент като обходен (в моят случай му задава стойност "*", тъй като матрицата съм я направил да е string[]. След маркирането на текущия елемент SearchPath извиква себе си за съседните 4 или по-малко елемента, които са в решетката и имат стойност равна на последно обходения елемент. При всяко извикване на SearchPath естествено си увеличавам текущата дължина на пътя с 1, а най-голямата дължина също естествено :) си я съхранявам в отделна променлива. В случая currentPathLength и maxPathLength съм си ги дефинирал като статични полета на класа, за да са ми по-лесно достъпни от всички методи в класа. Не че не могат да се декларират и като обикновени променливи в Main метода, но така ми се стори по-удобно за писане поне :). В началото и на всеки ход принтирам текущите стойности в матрицата, за да може по-лесно да се види как работи алгоритъма. Ако някой има въпроси по алгоритъма и конкретната имплементация ще се радвам да помогна :)
Поздрави!
Деян

от d_p_y (712 точки)


0

 

Ето и от мен едно решениице. Ползвал съм  Breadth-first search

 ( www.youtube.com/watch?v=6AKqv9c8l3o )

В конкретния случай опашката (Queue) върши страхотна работа.

В кода има подробен коментар.. препоръчвам и видеотo.

http://pastebin.com/YSkAzgG7


от psabinski (129 точки)


0

Написах решение без да гледам предложените в презентацията алгоритми, ако някой не се справя с разбирането им може да погледне това решение  с рекурсия.

 

http://pastebin.com/fwXKErpd




0

Largest area of equals с Depth-first search. Подробно обяснение на алгоритъма.


от kdikov (3407 точки)


0
Решението ти е хубаво, но единствената препоръка, която мога да ти дам е да направш матрицата от стрингове и да маркираш с "*"(или нещо друго), защото мисля, че с този код, ако най-дългата редица е от нули, няма да ти ги брои :)

от kirov (4821 точки)


3

Това е моето решение, като има коментари в кода, които ще помогнат :)

http://pastebin.com/Uwv7Aert


от ScorpS (1542 точки)


0
Браво колега, много простичко, добре коментирано и лесно за разбиране. Поздравявам те!

от ivan.yosifov (679 точки)


1

Приложение в реалния живот на следната задача :)
 

Facebook’s Graph Search Is the Future of Facebook

http://techland.time.com/2013/01/15/facebooks-graph-search-is-the-future-of-facebook/


от vlad0 (6103 точки)


1

Моето решение е с bread-first search (с който се сблъсквам за първи път и се оказа мн интересно и за разбиране и за имплементиране).

Обяснил съм в http://gparlakov.wordpress.com/2013/01/15/breadth-first-search-algorithm-in-c-multidimensional-arrays-problem-7/, като накратко:

Имам 1 матрица с числата и размер numbers[n,m], oще една със същия размер но с тип char visited[n,m] в която отбелязвам с 'y' тези който съм "посетил", и матрица за опашката с размер  queue[2,n*m] в горния и долния ред на индекс queueIndex която пазя съответно реда и колоната на следващият елемент от опашката(демек queue[0,queueIndex]  и queue[1,queueIndex]). 

 


от gparlakov (884 точки)


1
След няколко часа мъчение, най-накрая успях да го направя. Това до сега май е най-трудната задача която съм срещал на домашните.
http://pastebin.com/R3jT3gjd

от stann1 (1378 точки)