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


10

Условие: We are given a matrix of strings of size N x M. Sequences in the matrix we define as sets of several neighbor elements located on the same line, column or diagonal. Write a program that finds the longest sequence of equal strings in the matrix. Решениеsource.

ha fifi ho hi
fo ha hi xx
xxx ho ha xx
 
s qq s
pp pp s
pp qq s
 
Обяснение: За всяка клетка броим следващите еднакви клетки в посоките: надясно, надолу, надясно и надолу. Няма смисъл да броим наляво или нагоре, защото вече сме ги преброили на предишните итерации. Запазваме дали вече сме минали в тази посока от по-голяма редица, за да не преброяваме всички по-малки подредици. Накрая отпечатваме дължината на най-дългата такава и нейната стойност.
 
Edit: Махнах побитовите операции и използвам цивилизован начин с тримерен масив по идея на zlatkov да проверя дали сме минали в тази посока - diff.



Отговори



6
Само едно предложение - включи в посоките се и обратния диагонал ( {1, -1}) за да обхванеш всички случаи :)

от Teodor92 (13062 точки)


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

от jasssonpet (6814 точки)

0
и аз го бях проспал този случаи с обратния диагонал...

от kdikov (3407 точки)


3

от zlatkov (580 точки)


0
.Equals е същото като == в този случай, нали? Има ли причина да използваш това? Има ли разлика в скоростта на двете (разбрах за разликата при начина на сравнение)?

от spareva (1375 точки)

0
Не, няма особена разлика. Когато използваш оператора == , той извиква метода Equals.

от zlatkov (580 точки)


0
А проблем ли е ако домашното е по подробно от колкото се иска :? В смисел поиграх си малко повече и при въвеждане на стринговете ми излиза това: 3 5 a b f f a b a b b f a b b g b
" f " - 2 neighbors (Horizontal ) " b " - 2 neighbors (Horizontal ) " b " - 2 neighbors (Horizontal ) " b " - 2 neighbors (Vertical ) " b " - 2 neighbors (Diagonal, LEFT to RIGHT ) " b " - 2 neighbors (Diagonal, LEFT to RIGHT ) " f " - 2 neighbors (Diagonal, LEFT to RIGHT ) " a " - 2 neighbors (Diagonal, LEFT to RIGHT ) " b " - 2 neighbors (Diagonal, LEFT to RIGHT ) " b " - 2 neighbors (Diagonal, RIGHT to LEFT ) " a " - 2 neighbors (Diagonal, RIGHT to LEFT ) " b " - 2 neighbors (Diagonal, RIGHT to LEFT ) " b " - 2 neighbors (Diagonal, RIGHT to LEFT ) a b f f a b a b b f a b b g b Press any key to continue . . .
Нали не е проблем да си дам това решение или трябва само един от отговорите да излиза на екрана :?

от i9q19 (55 точки)


0
За домашните не е проблем, но за изпита ще е проблем.

от jasssonpet (6814 точки)


0
Според мен за тази задача е доста подходящо да се ползва рекурсия.

от RamiAmaire (1868 точки)


3

Ето и моето решение,  доста лаишко, но пък авторско и работещо (доколкото го тествах :) Правя 4 проверки  - по редове, колони, диагоналите започващи от [0,0] и в дясно от него и последната проверка е диагоналите в ляво от [0,0]. Все още ми е малко трудно да схвана дадените по-горе доста по-прилично изглеждащи решения, но се надявам с времето и аз да започна да пиша поне горе-долу подобен код (макар че идеята ми не е да ставм програмистче :) Иначе всякакви съвети са добре дошли :)   


от eandmir (457 точки)


1
Ето го и моето решение на задачата: http://pastebin.com/7HHQGPz4

от werew (576 точки)


0

Хах бая ме поизпоти тая задача...голямо нагласяне и проверки паднаха...Ето и моя код със методи, за да е по-четлив кода. Обхващам всички посоки. Изцяло авторско решение...има насочващи коментари в кода...

Е, не е като на jasssonpet, ама той ми е идол все пак, ако можех да пиша неговите красоти намаше да ми е идол :)

LineColumnOrDiagonal


от zhelyazkovn (2949 точки)


0
и на мен ми е идол :)



0
Това е моето решение - http://pastebin.com/tGtirU0x
Обхождам матрицата в четири посоки - по редове, по колони, по диагонал от ляво на дясно и по диагонал от дясно на ляво. Събирам елементите за съответната посока във временен едномерен масив, който се подава като аргумент на метод който прави следното - намира дали има повтарящи се последователно елементи в него и връща най-големият брой повтарящ се елемент. Ако последният намерен брой е по-голям от предходният, то той става последен.
Накрая програмата печати броя на най-много повтарящ се елемент, самият елемент и къде е намерен (в ред, колона или диагонал), в привен случай издава съобщение, че не е намерен повтарящ се елемент.

от szaekov (155 точки)


0
Не работи правилно за "a b c b d b". Връща 3, а трябва да е 1.

от jasssonpet (6814 точки)

0
Това е така, защото имаше сортиране на масива., което беше ненужно. Поправил съм го в http://pastebin.com/tGtirU0x. Относно примера - a b c b d b, смятам че програмата трябва да върне - 0, тъй като няма повтарящ се елемент повече от един път последователно.

от szaekov (155 точки)


0

Предложение за допълнителна оптимизация - до моя идол jasssonpet и всички които имат време и желание да се позанимават :)

Хареса ми идеята, ако елемент е част от вече проверена редица (т.е. има същия елемент непосредствено преди него в една от 4те посоки на движение) да не се проверява наново, защото няма смисъл. Но според мен е добре и дължината на вече намерената максимално дълга редица от еднакви елементи да оказва влияние при итерацията в масива. Идеята е следната:

Да приемем, че в посочения по-горе масив, всички клетки на първия ред имат една и съща стойност. Промените са в син цвят:

ha ha ha ha
fo ha hi xx
xxx ho ha xx

Тогава, при хоризонтална проверка на първия ред достигаме до 4 повторения, което не е възможно да се достигне при проверка по вертикала или 2та диагонала (броя елементи на ред са повече от тези на колона в конкретния случай). Също така, ако при еднаква дължина се вади само първия елемент със съответната дължина, дори и проверка по редове не е нужна, защото не може да има елемент с повече от 4 повторения.

Примера беше елементарен, но се надявам да съм обяснил добре идеята. Крайната стойност при итерация на масив в цикъл би трябвало да се коригира с дължината на вече намерената максимална редица от повтарящи се елементи.

 




0
Благодаря, може и това да се добави.

от jasssonpet (6814 точки)


8

- Една променлива пази текущия брояч на повторения;

- една пази максималния брой повторения;

- една пази кой елемент е с най-много повторения;

- една пази в каква посока се повтаря елемента;

Имам четири групи цикли за четирите посоки - хоризонтално дясно, вертикално надолу, диагонал надолу ляво, диагонал надолу дясно.

След като минат четирите цикъла, в зависимост от това в коя посока се е повтарял елемента използвам switch state, за да отпечатам кой елемент колко пъти в коя посока се е повтарял.

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

КОД


от AlexPopov (1568 точки)


0
Тъкмо се канех да поствам моя вариант и гледам, че логиката ми съвпада с твоята :) Great minds think alike :) +1

от vanina_nenova (327 точки)

0
На мен по-скоро ми се струва, че Great minds think like jasssonpet :)

от Tsanko (139 точки)