1 #include <iostream> 2 #include <sstream> 3 #include <string> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 #define GI ({int _t; scanf("%d", &_t); _t;}) 10 #define FOR(i, a, b) for (int i=a; i<b; i++) 11 #define REP(i, a) FOR(i, 0, a) 12 template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();} 13 int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;} 14 #define DBGV(_v) { REP(_i, _v.size()) { cout << _v[_i] << "\t";} cout << endl;} 15 #define OK(x,y) (x>=0 && y>=0 && x<cur && y<cur) 16 typedef pair<int,int> PII; 17 int main() { 18 string cnt, t; 19 int kase = 0; 20 while (cin >> cnt) { 21 kase++; 22 int cur = toInt(cnt); 23 vector <int> t1 (cur, 0); vector < vector < int > > grid(cur, t1); 24 vector <bool> t2 (cur, false); vector < vector < bool > > visited(cur, t2); 25 REP(i, cur) { 26 cin >> t; 27 REP(j, t.size()) { 28 if (t[j] == '1') { 29 grid[i][j] = 1; 30 } 31 else if (t[j] == '0') { 32 grid[i][j] = 0; 33 } 34 } 35 } 36 //REP(i, cur) { REP(j, cur) cout << grid[i][j] ; cout << endl; } 37 int res = 0; 38 REP(i, cur) { 39 REP(j, cur) { 40 if (grid[i][j] == 1 && visited[i][j] == false) { 41 //cout << i << "\t" << j << endl; 42 res++; 43 // Do a BFS here and visit nodes 44 queue <PII> q; 45 q.push(PII(i, j)); 46 visited[i][j] = true; 47 while (!q.empty()) { 48 PII node = q.front(); 49 q.pop(); 50 for (int dx=-1; dx<=1; dx++) { 51 for (int dy=-1; dy<=1; dy++) { 52 if (dx==0 && dy==0) continue; 53 if (OK(node.first+dx, node.second+dy) && grid[node.first+dx][node.second+dy] == 1 54 && visited[node.first+dx][node.second+dy] == false) { 55 q.push(PII(node.first+dx, node.second+dy)); 56 visited[node.first+dx][node.second+dy] = true; 57 } 58 } 59 } 60 61 } 62 } 63 } 64 } 65 printf("Image number %d contains %d war eagles.\n", kase, res); 66 } 67 return 0; 68 }