Uva 352 Solution

#include<bits/stdc++.h>

#define pii pair<int, int>

#define N 30

using namespace std;

int x[] = {-1, -1, -1, 0, 0, 1, 1, 1};

int y[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int row, v[N][N], cnt = 0;

char a[N][N];

bool check(int r, int c)

{

return (r >= 0) && (r < row) && (c >= 0) && (c < row);

}

void bfsvisit(int x1, int y1)

{

v[x1][y1] = 1;

queue<pii>q;

q.push(pii(x1, y1));

while(!q.empty())

{

pii r = q.front();

q.pop();

for(int i=0;i<8;i++)

{

int tx = r.first + x[i];

int ty = r.second + y[i];

if(check(tx, ty) && a[tx][ty] == '1' && v[tx][ty] == 0)

{

v[tx][ty] = 1;

q.push(pii(tx, ty));

}

}

}

}

void clear1()

{

for(int i=0;i<N;i++)

{

for(int j=0;j<N;j++)

{

a[i][j] = '\0';

v[i][j] = 0;

}

}

}

int main()

{

int k = 1;

while(cin >> row)

{

clear1();

cnt = 0;

for(int i=0;i<row;i++)

{

for(int j=0;j<row;j++)

{

cin >> a[i][j];

}

}

for(int i=0;i<row;i++)

{

for(int j=0;j<row;j++)

{

if(a[i][j] == '1' && v[i][j] == 0)

{

cnt++;

bfsvisit(i, j);

}

}

}

cout << "Image number " << k++ << " contains " << cnt << " war eagles.\n";

}

return 0;

}