IMPA/p352/p352.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>
#include <list>

using namespace std;

typedef unsigned int nat;

void flood_fill(vector<vector<nat>> &bitmap, nat x, nat y, nat color = 0)
{
    nat original_color = bitmap[x][y];
    //cout << "Flood_fill(" << x << ", " << y << ", " << color << ") original color = " << original_color << endl;

    queue<pair<int,int>> bf;
    bf.push({x, y});

    while(!bf.empty())
    {
        //cout << "Size: " << bf.size() << endl;
        pair<int,int> tile = bf.front();
        bf.pop();

        bitmap[tile.first][tile.second] = color;

        for(int i = tile.second-1; i <= tile.second+1; ++i)
        {
            for(int j = tile.first-1; j <= tile.first+1; ++j)
            {

                if(x == 3 && y == 0)
                {
                    //cout << "checking x: " << j << "  y: " << i << endl;
                }

                if(i >= 0 && i < bitmap.size() && j >= 0 && j < bitmap[0].size() && bitmap[j][i] == original_color)
                {
                    //cout << j << ", " << i << " : " << bitmap[j][i] << " <= " << color << endl;
                    bf.push({j,i});
                    bitmap[j][i] = color;
                    //cout << "Dude wtf?!" << j << ", " << i << " : " << bitmap[j][i] << " == " << color  << endl;
                }
            }
        }
    }
}

void print_grid(const vector<vector<nat>> &bitmap)
{
    for(auto row : bitmap)
    {
        for(auto cell : row)
        {
            cout << cell;
        }
        cout << endl;
    }
}

int main()
{
    nat grid_size, num = 1;

    while(cin >> grid_size)
    {
        cin.ignore(1000,'\n');
        vector<vector<nat>> grid(grid_size, vector<nat>(grid_size, 0));

        nat num_eagles = 0;

        for(nat y = 0; y < grid_size; ++y)
        {
            string str;
            getline(cin, str);
            for(nat x = 0; x < grid_size; ++x)
            {
                if(str[x] == '1')
                    grid[y][x] = 1;
            }
        }

        //print_grid(grid);
        //cout << endl;

        for(nat y = 0; y < grid_size; ++y)
        {
            for(nat x = 0; x < grid_size; ++x)
            {
                if(grid[x][y] == 1)
                {
                    ++num_eagles;
                    flood_fill(grid, x, y, 0);
                    //print_grid(grid);
                    //cout << endl;
                }
            }
        }


        cout << "Image number " << num++ << " contains " << num_eagles << " war eagles." << endl;

    }

    return 0;
}