Algorithm...

[Krofna]

The problem I am trying to solve is following (poor translation in 3..2..)

Your task is to spread as much as klingons possible in a hotel of size X*Y such that no klingon can hear each others snoring. Snoring can penetrate C walls (diagonal is 2 walls).
Input: X Y C
Output: Max klingons that can fit in hotel

Idea behind my solution was following:
1) Pick the room which will cause lowest number of other rooms to be affected by noise and put a klingon in it.
2) Repeat 1) untill all rooms are affected by noise

Problem is: Works only on some inputs.

Sample I/O:
I: 5 5 2, O: 6
I: 4 7 3, O: 5
I: 5 7 1, O: 18

What did I do wrong?

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#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 decrease_key(Node* pNode)
    {
        for (int i = 0; i < this->c.size(); ++i)
        {
            if (this->c[i] == pNode)
            {
                push_heap(this->c.begin(), this->c.begin() + i + 1);
                break;
            }
        }
    }
};

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

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

Hotel::Hotel() : R(0)
{
    cin >> X >> Y >> B;
    G.resize(Y, vector<Node>(X, Node()));
    L.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()
{
    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;
            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]);
    }
}

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)
                    ++Cijena;
    return Cijena;
}

void Hotel::Relax(Node* pIzvor, Node* pTrenutna)
{
    switch (pTrenutna->B)
    {
        case BIJELA:
            pTrenutna->B = SIVA;
            L[LI++] = pTrenutna;
            break;
        case SIVA:
            pTrenutna->C = Cijena(pTrenutna);
            O.decrease_key(pTrenutna);
            break;
        default:
            break;
    }
}

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 * 2)
                	Relax(pIzvor, &G[y][x]);
            }
        }
    }
}

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

[Sandermatt]

I am not sure how others see it, but for me it would help if you could translate the words: Boja, BIJELA , SIVA, CRNA, Rasporedi, NapraviBuku, IzracunajCijene, Cijena .

[Program Programmer]

i will: Boja = Color BIJELA = White SIVA = Grey CRNA = Black Rasporedi = Arange (i dont know if i translated that quite right) NapraviBuku = MakeNoise
IzracunajCijene = CalculatePrices Cijena = Price

[Krofna]

That is correct, Program Programmer.
Also: pIzvor = pSource , pTrenutna = pCurrent , Udaljenost = Manhattan Distance (Altho these are obvious from the context)

[Sandermatt]

I would say look at:

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)
++Cijena;
//cout << pNode->P.x << " " << pNode->P.y << " " << Cijena << "\n";
return Cijena;
}


In the for loops you need a smaller or equal than sign instead of an equal sign.

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)
++Cijena;
//cout << pNode->P.x << " " << pNode->P.y << " " << Cijena << "\n";
return Cijena;
}