A trie fa (trie tree, radix tree, prefix tree) egy olyan adatszerkezet, amelyben sztringek tárolhatók, és azok prefix alapján könnyen kereshetők.
Jobb oldalt látható egy ilyen fa, amely a tea, ten, in és inn
szavakat tartalmazza. A t, te és i sztringek nincsenek a fában; csak az
előbbi szavakhoz vezető út miatt kellett létrehozni őket.
Írj programot, amely ilyen szótárat épít az STL eszközeivel. Lehessen egy egyszerű felületen hozzáadni a szavakat, és ellenőrizni, benne vannak-e a szótárban!
A sakk tisztjei az alábbi módokon tudnak mozogni:
- A bástya azonos soron vagy oszlopon léphet.
- A futó azonos átlón léphet.
- A vezér bástyaként és futóként is tud lépni.
- Végül pedig a huszár az egyetlen, amely el tud menekülni a vezér elől, mert L alakban (2-t erre, 1-et arra) lép.
Olyan programot kell írnod, amelyben feladat megmondani egy kiválasztott mezőn álló figuráról, hogy támadja-e valamelyik másik figurát a táblán. A színekkel (világos, sötét) most nem kell foglalkoznod.
Procedurálisan
Készíts ehhez procedurális modellt! Ebben egy mezőn álló figura típusát egy felsorolt típusú értékkel enum-mal
tárolhatod, amelynek része kell legyen az üres mező is. A tábla ilyen enum-ok tömbje. Írd meg azt a függvényt,
amely egy pozíciót kap, és igaz/hamis értékkel tér vissza attól függően, hogy van-e ott figura ÉS támad-e az egy másik figurát!
Objektumorientáltan
Az objektumorientált modellben a tábla olyan objektumokból áll, amelyek mind egy figura ősosztály leszármazottjai. A tábla így egy heterogén kollekció, amely 8×8 pointerből áll; az üres mező lehet null pointer is. A lépést pedig valamilyen virtuális függvény adja meg. Írd meg így is a programot!
Végül hasonlítsd össze a két programot olyan szempontból, hogy mennyire különülnek el a programban az egyes önálló tevékenységek függvényei!
Megoldás
#include <iostream>
class Table;
class Piece {
public:
/* igazzal tér vissza, ha a megadott mezőre tud mozogni a figura */
virtual bool can_move(int x, int y) const = 0;
/* igazzal tér vissza, ha bármit épp támad */
bool attacks_something() const;
/* táblán elhelyezés */
void set_pos(Table *table, int x, int y) {
table_ = table;
x_ = x;
y_ = y;
}
protected:
int x_, y_;
Table *table_;
};
class Table {
public:
Table() {
for (int y = 0; y < 8; ++y)
for (int x = 0; x < 8; ++x)
table_[y][x] = nullptr;
}
void set(int x, int y, Piece *p) {
table_[y][x] = p;
p->set_pos(this, x, y);
}
Piece *get(int x, int y) const {
return table_[y][x];
}
private:
Piece *table_[8][8];
};
bool Piece::attacks_something() const {
/* mit támad? */
for (int y = 0; y < 8; ++y) {
for (int x = 0; x < 8; ++x) {
/* saját magát nem */
if (x == x_ && y == y_)
continue;
/* ha van ott valami, és én léphetek oda, akkor támadom. */
/* az algoritmus független a típustól! */
if (table_->get(x, y) && this->can_move(x, y))
return true;
}
}
return false;
}
class Rook : public Piece {
public:
virtual bool can_move(int x, int y) const {
return x == x_ || y == y_;
}
};
class Bishop : public Piece {
public:
virtual bool can_move(int x, int y) const {
return abs(x - x_) == abs(y - y_);
}
};
class Queen : public Piece {
public:
virtual bool can_move(int x, int y) const {
return x == x_ || y == y_ || abs(x - x_) == abs(y - y_);
}
};
class Knight : public Piece {
public:
virtual bool can_move(int x, int y) const {
int dx = abs(x - x_);
int dy = abs(y - y_);
return (dx == 2 && dy == 1) || (dx == 1 && dy == 2);
}
};
int main() {
Table t;
Rook r1;
Rook r2;
t.set(5, 5, &r1);
t.set(6, 6, &r2);
std::cout << r1.attacks_something();
}