Zmi(ji)ca

Napisati generičku klasu zmica<N> koja implementira igru zmica na tabli dimenzija N x N. Klasa treba da podržava sledeće operacije:

zmica() - konstruktor koji kreira zmica igru sa početnim položajem glave zmice u gornjem levom uglu table i nasumično postavljenom hranom na tabli.
void ispisi() const - ispisuje trenutno stanje table na standardni izlaz. Glava zmice se označava sa G, telo zmice sa O, hrana sa H, a prazna polja sa ..
bool pomeri(char smer) - pomera zmicu u datom smeru (U - gore, D - dole, L - levo, R - desno). Ukoliko zmica pojede hranu, st njena dužina se povećava za 1 i vraća se true. Ukoliko zmica udari u zid ili samu sebe, igra se završava i vraća se false. U ostalim slučajevima vraća se true.

Funkcija promeri treba da radi u vremenskoj složenosti $O(1)$. Dok memorijska složenost treba da bude $O(n)$, gde je $n$ trenutna dužina zmice.

Ulaz

Sa standardnog ulaza se učitavaju naredbe u formatu:

U - pomera zmicu gore.
D - pomera zmicu dole.
L - pomera zmicu levo.
R - pomera zmicu desno.

Početno seme za nasumični broj generator treba postaviti na srand(42).

Izlaz

Na standardni izlaz se ispisuje stanje table nakon svake naredbe. Ukoliko zmica udari u zid ili samu sebe, ispisuje se poruka Kraj igre! kao i trenutni skor (dužina zmice).

Primer

`stdin`

D
R
R
R
D
L
U

`stdout`

G . . . . 
H . . . . 
. . . . . 
. . . . . 
. . . . . 

O . . . . 
G H . . . 
. . . . . 
. . . . . 
. . . . . 

O . . . . 
O G . . . 
. . . H . 
. . . . . 
. . . . . 

. . . . . 
O O G . . 
. . . H . 
. . . . . 
. . . . .

. . . . . 
. O O G . 
. . . H . 
. . . . . 
. . . . .

. . . . . 
H O O O . 
. . . G . 
. . . . . 
. . . . . 

. . . . . 
H . O O . 
. . G O . 
. . . . . 
. . . . . 

. . . . . 
H . O O . 
. . G O . 
. . . . . 
. . . . . 
U
Kraj igre!
Skor: 4

Rešenje

`main.cpp`

#include <iostream>
#include <deque>
#include <unordered_set>
#include <utility>
#include <random>

namespace matf
{
	/* Klasa za igru zmicu dimenzije NxN */
	template <size_t N>
	class zmica
	{
		typedef std::pair<size_t, size_t> Polje;

		public:
			/* Inicijalizacija zmice */
			zmica()
			{
				hrana = { rand() % N, rand() % N };
				if (hrana.first == 0 && hrana.second == 0) {
					hrana = {0, 1};
				}

				polja_zmice.push_back({0, 0});
				zauzeta_polja.insert({0, 0});
			}

			/* Pomera zmicu u datom pravcu: 
			 * 'U' - gore, 'D' - dole, 'L' - levo, 'R' - desno 
			 */
			bool pomeri(const char pravac)
			{
				Polje nova_glava = polje_nove_glave(pravac);

				// Provera sudara sa zidom
				if (nova_glava.first >= N || nova_glava.second >= N) {
					return false;
				}

				// Provera sudara sa samom zmicom
				if (zauzeta_polja.find(nova_glava) != zauzeta_polja.end()) {
					return false;
				}

				if (nova_glava == hrana) { // pojedena hrana
					hrana = { std::rand() % N, std::rand() % N };
				} else { // uklanjanje repa
					Polje stari_rep = polja_zmice.back();
					polja_zmice.pop_back();
					zauzeta_polja.erase(stari_rep);
				}

				// Dodavanje nove glave
				polja_zmice.push_front(nova_glava);
				zauzeta_polja.insert(nova_glava);

				return true;
			}

			/* Ispis trenutnog stanja igre */
			void ispisi() const
			{
				// Ciscenje ekrana (samo za Unix-like sisteme, za Windows koristiti "cls")
				system("clear");

				for (size_t i = 0; i < N; i++) {
					for (size_t j = 0; j < N; j++) {
						Polje trenutno_polje = {i, j};
						if (trenutno_polje == polja_zmice.front()) {
							std::cout << "G "; // glava zmice
						} else if (zauzeta_polja.find(trenutno_polje) != zauzeta_polja.end()) {
							std::cout << "O "; // telo zmice
						} else if (trenutno_polje == hrana) {
							std::cout << "H "; // hrana
						} else {
							std::cout << ". "; // prazno polje
						}
					}
					std::cout << std::endl;
				}
			}

			size_t skor() const
			{
				return polja_zmice.size();
			}

		private:
			/* Racuna polje nove glave zmice na osnovu pravca kretanja */
			Polje polje_nove_glave(const char pravac) const
			{
				Polje nova_glava = polja_zmice.front();
			
				switch (pravac) {
					case 'U':
						nova_glava.first--;
						break;
					case 'D':
						nova_glava.first++;
						break;
					case 'L':
						nova_glava.second--;
						break;
					case 'R':
						nova_glava.second++;
						break;
					default:
						throw std::invalid_argument("Nepoznat pravac kretanja");
				}

				return nova_glava;
			}

		private:
			// Hash functor za tip Polje (pair<size_t, size_t>)
			struct polje_hash {
				size_t operator()(const Polje &p) const noexcept {
					return std::hash<size_t>{}(p.first) ^ (std::hash<size_t>{}(p.second) << 1);
				}
			};

		private:
			std::deque<Polje> polja_zmice;
			std::unordered_set<Polje, polje_hash> zauzeta_polja;
			Polje hrana;
	};
};

int main(void)
{
	srand(42);

	matf::zmica<5> zmica;

	zmica.ispisi();

	char pravac;

	while (std::cin >> pravac) {
		try {
			if (!zmica.pomeri(pravac)) {
				std::cout << "Kraj igre!" << std::endl;
				std::cout << "Skor: " << zmica.skor() << std::endl;
				break;
			}
		} catch (const std::invalid_argument& e) {
			std::cerr << e.what() << std::endl;
		}

		zmica.ispisi();
	}
	

	return 0;
}