Este é um problema de grafos que pode ser resolvido contando a quantidade de componentes conectados (http://bit.ly/1yGPXQk).
Além disso, esse problema também necessita de uma abordagem diferente para representar o grafo. Ao invés de uma lista de adjacencias, é dada
uma matriz. Assim, podemos já imaginar cada célula da matriz como sendo um vértice e os 8 nós vizinhos como sendo seus adjacentes. Sendo assim, criamos uma função que retorna uma lista de adjacencias, ao invés de criar uma matriz.
Dessa vez, coloquei parte do meu código para dar uma ideia de como modelei o problema.
Agora você vai precisar implementar a busca em profundidade [teoria][implementação] no grafo e também contar a quantidade de componentes conectados [ideia e implementação].
#include <iostream>#include <utility>#include <vector>#include <cstring>using namespace std;#define WHITE 0#define GRAY 1#define BLACK 2#define DIM_Y 25#define DIM_X 26typedef pair<int,int> pii;typedef vector<pii> vpii;#define TRvppi(v, it) \ for (vpii::iterator it = v.begin() ; v.end()!=it ; ++it)/*O problema indica que a dimensão não excede 25. Deixamos um a mais para o \0*/char image[DIM_Y][DIM_X];int visit_status[DIM_Y][DIM_X];int dimension;vpii adj_list(pii *p){ vpii adjs; int y[] = {-1,-1,-1,0,1,1,1,0}; int x[] = {-1,0,1,1,1,0,-1,-1}; for (int i=0; i< 8; ++i) { int ny = p->first + y[i]; int nx = p->second + x[i]; if (ny>=0 && ny<dimension && nx >=0 && nx<dimension && image[ny][nx] == '1') { pii ad(ny, nx); adjs.push_back(ad); } } return adjs;}void dfs(pii *s){ // seu código aqui}