Grid feladat segítség kellene?

"Állásinterjún voltam ma és volt ilyen kérdés: 1000x1000-es griden 0 jelzi a bejárható cellákat és 1 a falakat. Egy darab fal cella kiütésével maximum mekkora lesz az egy pontból bejárható terület ha jobbra/balra/le/fel mozoghatunk és falon nem mehetünk át?"

A max bejárható terület az 1000*1000 - falak_szama - 1 de kétlem, hogy ez lenne a kérdés.

Nagyon képfeldolgozás/gépli látás szagú feladat de nem teljesen világos mit kell meghatározni itt.

#9 válasza azért nem jó mert egy fal kiütésével akár 4 elkülönített területet is egybe lehet olvasztani (4 szomszédság miatt) de ő csak párokat vizsgál.

Pl. itt a középső eltávolitása:

101

010

101

Szerintem itt bináris képekre használt algoritmusokkal érdemes dolgozni. Na itt kezdenek bonyolódni a dolgok mert objektum (bejárható terület) címkézéséhez 2 módszerről is tudok.

Rekurzív - lehet párhuzamosítani.

Szekvenciális - egyszerű, párhuzamosítható de nem kell a teljes képet a memóriába tölteni (inkább microkontroller-eknél van jelentősége).

Címkézés után meg lehet határozni az objektumok méretét (erre is vannak kész megoldások), ezután végig kell menni minden fal elemen és megnézni mivel határosak. Itt lehet csinálni egy max kiválasztást ahol azoknak a bejárható területeknek az összegét veszed amivel határos a fal.

Kész! Valszeg van optimálisabb megoldás is.

Szekvenciális alatt erre hivatkoztam:

[link]

annyi a különbség hogy a példában 8 szomszédosságot használnak neked viszont 4 kell