sprawdzenie czy 0 jest otoczone 1

Witam , potrzebuje sprawdzic czy w tablicy o wymiarach NxM wystepuje sytuacja ,ze 0 jest otoczone z wszystkich stron przez 1(z gory,dolu i po skosach).
0-a moga wystepowac w grupie,wtedy skajne zera z grupy musza spelniac poprzedni warunek. Krawiedzie tablicy sa wypelnione 0 zawsze.

np. Pogrubione 0 naleza do poszukiwanej grupy.

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 0 0 1 0
0 1 0 1 1 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

Moze ktos ma do podrzucenia jakis pomysl??

Lecimy przez tablicę po kolei i puszczamy BFS dla każdego 0 które jeszcze nie było oznaczone. Mamy 3 oznaczenia:

• nieodwiedzony wierzchołek
• wierzchołek odwiedzony,
• wierzchołek odwiedzony, należący do grupy stykającej się z krawędzią
  Jeśli w BFS trafimy na krawędź to wszystkie wierzchołki z tej grupy oznaczamy jako stykające się z krawędzią
  Jeśli w BFS trafimy na wierzchołek który należy do grupy stykającej się z krawędzią to zaliczamy ten wierzchołek jak i wszystkie stykające się z nim jako stykające się z krawędzią
  Jeśli w BFS skończą nam się wierzchołki (oznaczyliśmy wszystkie 0 w przylegające do siebie) i nie trafiliśmy na wierzchołek stykający się z krawędzią to znaleźliśmy grupę zer otoczoną jedynkami.
  W ten sposób w czasie nie większym od O(8n) i w pamięci O(3n), gdzie n=N*M, znajdziemy odpowiedź.

Skoro zera mogą stać obok siebie, byle by były otoczone jedynkami, to wystarczy sprawdzić, czy jakieś zero stoi przy krawędzi tablicy. Dowolny układ zer jest dozwolony, ale nigdy nie będzie miał elementów w kolumnach i wierszach: lewa+1, gorna+1, lewa-1, dolna-1.

sprawdzic czy w tablicy o wymiarach NxM wystepuje sytuacja ,ze 0 jest otoczone z wszystkich stron przez 1

Gdyby chodziło o sprawdzenia czy są zera nieotoczone 1 to oczywiście że wystarczyłoby sprawdzć tylko krawędzie ;] ale treść zadania jest innna ;)