Házi feladat segítségre lenne szükségem?

Sziasztok, 10-es voltam, reflektálnék a saját válaszomra, mert most már azt is elolvastam, mi volt pontosan a kérdés, illetve a feladat.

"Nem veszi figyelembe azt az esetet, ha a mátrix minden mezőjében 1-es áll, azt hiszem, nem is az a lényeg..." -> nem is kell, a feladat szövege szerint garantáltan van 0 a mátrixban.

A csatolt algoritmus nem számolja bele a maximális számba azt a mezőt, ahol maga a hangszóró van, de eggyet már hozzá tudunk adni.

Mivel nem kész megoldást kértél, ne nézd meg a kódot, inkább segítségképp: Minden mezőre a szomszédos 4 mezőből számold a hangszóró által elérhető mezők számát. Mindezt tedd rekurzívan, és ezáltal észreveheted, hogy tipikusan DP-sal megoldható feladatról van szó.

Szia. Örülök, hogy kaptál jobbat. A megoldásom valószínűleg nem optimális, biztosan van attól jobb, de attól még O(n^2) időbonyolultságú. (Ez nem 1 futtatás időszükségletéből mérhető, hanem az időszükségletnek a bemenet méretétől függő változásának tendenciájából.)

Amúgy titkos az a 15 siris algoritmus, vagy esetleg okulhatunk belőle mi is? (Nem is értem, miért privátban kell megoldást nyújtani egy publikus kérdésre egy anonim oldalon.)

#14 nem negyzetes az algoritmusod.

Minden elemen vegig mesz, ez n*n nyilvan, viszont az elemeken nem konstans muveleteket hajtasz vegre.

Ugy latom probaltal valami memoization-feleseget implementalni, (valoszinuleg ezert gondolod, hogy negyzetes a komplexitas), de ettol minden egyes oszlopra meghivod pl. a GetAccessibleCellsOnBottom metodust (ami vegig megy mind az n soron) es minden egyes sorra a GetAccessibleCellsOnRight-ot (ami hasonlokeppen vegig megy n oszlopon).

16-os, jogos amit írsz, abszolút meggyőztél, köszönöm a magyarázatot!

Kérdező, van valami speciális oka, hogy nem osztod meg velünk az algoritmust, amit kaptál?

Szép napot mindenkinek!