Klingonci.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;

#define DEBUG

enum Boja
{
    BIJELA  = 0, // Nije pronađeno
    SIVA    = 1, // Pronađeno
    CRNA    = 2 // Buka
};

struct Vector2i
{
    Vector2i() { }
    Vector2i(int x, int y) : x(x), y(y) { }
    int x;
    int y;
};

struct Node
{
    Node()
    {
        B = BIJELA;
    }
    Boja B;
    int C;
    Vector2i P;
};

struct CompareNode : public binary_function<Node*, Node*, bool>
{
    bool operator()(const Node* pFirst, const Node* pSecond) const
    {
        return pFirst->C > pSecond->C;
    }
};

// Dirty implementation of heap: TODO: replace with a proper one
class Heap : public priority_queue<Node*, vector<Node*>, CompareNode>
{
public:
    void heapify()
    {
        make_heap(this->c.begin(), this->c.end(), CompareNode());
    }
};

class Hotel
{
public:
    Hotel();
    void Rasporedi();
    void NapraviBuku(Node* pIzvor);
    void IzracunajCijene();
    int Cijena(Node* pNode);

private:
    vector<vector<Node> > G;
    vector<Node*> L, L2;
    Heap O;
    int X, Y, B, R, LI, LI2;
};

Hotel::Hotel() : R(0)
{
    cin >> X >> Y >> B;
    G.resize(Y, vector<Node>(X, Node()));
    L.resize(Y * X); L2.resize(Y * X);

    for (int y = 0; y < Y; ++y)
        for (int x = 0; x < X; ++x)
            G[y][x].P = Vector2i(x, y);
}

void Hotel::Rasporedi()
{
	if (B == 0)
	{
		cout << X * Y << endl;
		return;
	}

    Node* pIzvor;

    // Kutevi imaju najmanju cijenu na pocetku
    G[0][0].C = Cijena(&G[0][0]);
    /*G[Y-1][0].C = Cijena(&G[Y-1][0]);
    G[0][X-1].C = Cijena(&G[0][X-1]);
    G[Y-1][X-1].C = Cijena(&G[Y-1][X-1]);*/
    O.push(&G[0][0]);
    /*O.push(&G[Y-1][0]);
    O.push(&G[0][X-1]);
    O.push(&G[Y-1][X-1]);*/

    while (!O.empty())
    {
        pIzvor = O.top();
        O.pop();
        if (pIzvor->B != CRNA)
        {
            LI = 0; LI2 = 0;
            NapraviBuku(pIzvor);
            IzracunajCijene();
#ifdef DEBUG
            cout << "Klingonac u sobi: " << pIzvor->P.x << " " << pIzvor->P.y << endl;
#endif
            ++R;
        }
    }

    cout << R << endl;
}

void Hotel::IzracunajCijene()
{
    for (int i = 0; i < LI; ++i)
    {
        L[i]->C = Cijena(L[i]);
        O.push(L[i]);
    }
    for (int i = 0; i < LI2; ++i)
    {
    	L2[i]->C = Cijena(L2[i]);
    }
    O.heapify();
}

int Hotel::Cijena(Node* pNode)
{
    int Cijena = 0;
    for (int y = pNode->P.y - B; y <= pNode->P.y + B; ++y)
        for (int x = pNode->P.x - B; x <= pNode->P.x + B; ++x)
            if (x >= 0 && y >= 0 && x < X && y < Y)
                if (G[y][x].B != CRNA)
                	if ((abs(x - pNode->P.x) + abs(y - pNode->P.y)) <= B)
                		++Cijena;
    return Cijena;
}

void Hotel::NapraviBuku(Node* pIzvor)
{
    for (int y = pIzvor->P.y - 2 * B; y <= pIzvor->P.y + B * 2; ++y)
    {
        for (int x = pIzvor->P.x - 2 * B; x <= pIzvor->P.x + 2 * B; ++x)
        {
            if (x >= 0 && y >= 0 && x < X && y < Y)
            {
            	int Udaljenost = abs(x - pIzvor->P.x) + abs(y - pIzvor->P.y);
                if (Udaljenost <= B)
                {
                    G[y][x].B = CRNA;
                }
                else if (Udaljenost == B + 1 && G[y][x].B == BIJELA)
                {
                	G[y][x].B = SIVA;
                	L[LI++] = &G[y][x];
                }
                else if (Udaljenost <= B * 2 && G[y][x].B == SIVA)
                {
                	L2[LI2++] = &G[y][x];
                }
            }
        }
    }
}

int main()
{
    Hotel Klingonci;
    Klingonci.Rasporedi();
    return 0;
}