mancha.cpp

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1123, MAXM = 1123; 

//vetores auxiliares
int dx[5] = {1, 0, -1, 0};
int dy[5] = {0, 1, 0, -1};

bool marc[MAXN][MAXM];
int imagem[MAXN][MAXM];
int componentes = 0;

int n, m;

void BFS(int i, int j){

	queue<pair<int, int> > fila; //na fila, guardamos as coordenadas das vértices
	fila.push(make_pair(i, j));
	marc[i][j] = true;

	while(!fila.empty()){
		int x = fila.front().first;
		int y = fila.front().second;
		fila.pop();
		
		for(int k = 0; k < 4; k++){
			int xatual = x + dx[k];
			int yatual = y + dy[k];
			
			//se ja visitamos o vizinhom ou ele não faz parte de um mancha,
			//avançamos para o próximo vizinho													
			if(marc[xatual][yatual] || !imagem[xatual][yatual]) continue;
			marc[xatual][yatual] = true;	
			fila.push(make_pair(xatual, yatual));

		}
	}

}


int main(){

	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> imagem[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(imagem[i][j] == 1 && !marc[i][j]){
				//se essa casa nao foi visitada, e faz parte de uma imagem, temos que encontrar todos os seus vizinhos
				componentes++;
				BFS(i, j);
			}

		}
	}
	cout << componentes << endl;


}