UVa 352 - The Seasonal War

// UVa 352 - The Seasonal War

#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;

int m[8][2] = { { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, 1 }, { 0, -1 }, { -1, 1 }, { -1, 0 }, { -1, -1 } };

struct pa {
	int a, b;
};

int main() {
	int n, t = 0;
	while (cin >> n) {
		t++;
		string mat[25];
		for (int i = 0; i < n; i++)
			cin >> mat[i];
		int sol = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (mat[i][j] == '1') {
					sol++;
					queue<pa> q;
					pa ini = { i, j };
					q.push(ini);
					mat[ini.a][ini.b] = '0';
					while (!q.empty()) {
						pa p = q.front();
						q.pop();
						for (int k = 0; k < 8; k++) {
							pa r = { p.a + m[k][0], p.b + m[k][1] };
							if (r.a >= 0 && r.a < n && r.b >= 0 && r.b < n && mat[r.a][r.b] == '1') {
								mat[r.a][r.b] = '0';
								q.push(r);
							}
						}
					}
				}
		printf("Image number %d contains %d war eagles.\n", t, sol);
	}
	return 0;
}