71aKTf - Online C++0x Compiler & Debugging Tool

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

const int N=1005;
int n, m, a[N][N], ans;
bool vst[N][N];

int di[4]={-1, 0, 1, 0};
int dj[4]={0, 1, 0, -1};

bool inside(int i, int j) //hàm kiểm tra ô (i, j) có nằm trong ma trận hay không
{
    return i>0 && i<=n && j>0 && j<=m;
}

void bfs(int u, int v)
{
    queue<pair<int, int>> q;
    q.push({u, v});
    vst[u][v]=1;
    while(!q.empty()){
        int i=q.front().first, j=q.front().second;
        q.pop();
        for(int k=0;k<4;++k){
            int ni=i+di[k], nj=j+dj[k];
            if(inside(ni, nj) && !vst[ni][nj] && a[ni][nj]==1){
                vst[ni][nj]=1;
                q.push({ni, nj});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin >> a[i][j];
        }
    }

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(!vst[i][j] && a[i][j]==1){
                ++ans;
                bfs(i, j);
            }
        }
    }

    cout << ans;
    return 0;
}