### Algorithm...

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?

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183`` ``````#include #include #include #include #include #include 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 { 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, 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 > G; vector L; Heap O; int X, Y, B, R, LI; }; Hotel::Hotel() : R(0) { cin >> X >> Y >> B; G.resize(Y, vector(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; }``````
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 .
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
That is correct, Program Programmer.
Also: pIzvor = pSource , pTrenutna = pCurrent , Udaljenost = Manhattan Distance (Altho these are obvious from the context)
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;
}
Topic archived. No new replies allowed.