Manchas.cpp

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

const int MAXN=1100, MAXM=1100; //declara o valor de MAXN e MAXM (máximo de N e M), que define o tamanho de outros vetores
int pixel[MAXN][MAXM]; //declara um vetor(pixel) de coordenada (MAXN,MAXM) 
bool visit[MAXN][MAXM]; //declara uma função para saber se um pixel já foi (true/0) ou não (false/1) analisado

int va[4]={1,0,-1,0}; //declara um vetor já com os valores de cada posição do vetor
int vb[4]={0,1,0,-1}; //declara um vetor já com os valores de cada posição do vetor

void BFS(int i, int j) 
{
	int a,b,k,newa,newb; //declara as variáveis utilizadas no BFS
	queue<pair<int,int> > fila; //declara um queue (fila) do tipo pair que armazena dois inteiros (2 int)
	fila.push(make_pair(i,j)); //insere o par (i,j) na fila 
	visit[i][j]=true; //determina a bool como true (verdade ou 0)
	while(!fila.empty()) //enquanto exitir elementos na fila (enquanto ela não estiver vazia)
	{
		a=fila.front().first; //a assume o valor do primeiro termo (i) do par na primeira posição da fila
		b=fila.front().second; //b assume o valor do segundo termo (j) do par na primeira posição da fila
		fila.pop(); //remove o primeiro elemento da fila, ou seja, o primeiro par é apagado (mas está salvo em a e b)
		for(k=0; k<4; k++) //k começa em 0 e enquanto é menor que quatro, ficamos nesse loop; no fim sempre é somado 1 na variável k
		{
			newa = a + va[k]; //newa assume o valor de a + o valor da posição 'k' no vetor de a 'va'
			newb = b + vb[k]; //newb assume o valor de b + o valor da posição 'k' no vetor de b 'vb'
			
			if(!visit[newa][newb] && pixel[newa][newb]) //se ainda não analisamos esse vizinho E ele é um pedaço de mancha (ou seja, na entrada ele seria 1)
			{
				visit[newa][newb]=true; //determina o vetor desse pixel como verdade, ou seja, como um pixel já analisado
				fila.push(make_pair(newa,newb)); //insere esse novo par de coordenadas na fila para depois analisar os seus pixels vizinhos também
			}
		}
	}
}

int main()
{
	int N,M,i,j,manchas=0; //declara as variáveis utilizadas na main()
	scanf("%d %d", &N, &M); //lê a primeira linha de entrada (M e N)
	for(i=1; i<=N; i++) //i começa sendo 1 e enquanto não é igual a N, ficamos nesse loop; no fim é somado 1 na variável i
	{
		for(j=1; j<=M; j++) //j começa sendo 1 e enquanto não é igual a M, ficamos nesse loop; no fim é somado 1 na variável j
		{
			scanf("%d", &pixel[i][j]); //lê todos os inteiros P, ou seja, os pixels (0 ou 1)
		}
	}
	for(i=1; i<=N; i++) //i começa sendo 1 e enquanto não é igual a N, ficamos nesse loop; no fim é somado 1 na variável i
	{
		for(j=1; j<=M; j++) //j começa sendo 1 e enquanto não é igual a M, ficamos nesse loop; no fim é somado 1 na variável j
		{
			if(!visit[i][j] && pixel[i][j]==1) //se esse pixel ainda não foi analisado E é um pedaço de mancha
			{
				manchas++; //soma 1 na variável manchas, ou seja, conta mais uma mancha na imagem 
				BFS(i,j); //observamos os pixels vizinhos desse pixel, ou seja, vamos para a void BFS()
			}
		}
	}
	printf("%d\n", manchas); //imprimi a resposta final = número de manchas 
	return 0; //retorna a 0
}