ManchasDePele.cpp

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;

//Matriz que guarda o tabuleiro
int grid[MAXN][MAXN];

//Matriz de marcação pra marcar quem já foi visitado
int marc[MAXN][MAXN];

//Truque DiDj, que vou explicar mais pra frente
int di[4] = {1,-1,0,0};
int dj[4] = {0,0,1,-1};

//Dimensões do tabuleiro
int N,M;

void dfs(int i, int j)
{
    //Marco que já visitei a casa atual
    marc[i][j] = 1;
    for(int k = 0; k < 4; k++)
    {
        //Truque DiDj
        int vizI = i + di[k];
        int vizJ = j + dj[k];

        //Checo se as coordenadas estão dentro do tabuleiro
        if(vizI > N || vizI <= 0 || vizJ > M || vizJ <= 0) continue;
        //Checo se a casa vizinha à atual está pintada ou não
        if(grid[vizI][vizJ] == 0) continue;

        //Checo se não foi visitado
        if(marc[vizI][vizJ] == 0) dfs(vizI,vizJ);
    }
}

int main()
{
    cin >> N >> M;

    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
            cin >> grid[i][j];
    }

    int componentes = 0;
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            //Checo é pintado e não foi visitado
            if(marc[i][j] == 0 && grid[i][j] == 1)
            {
                componentes++;
                dfs(i,j);
            }
        }
    }

    cout << componentes;
}