Zrób słownik std::pair<int, int> -> int i wtedy masz czas stały.
Pamiętaj o tym, że STL nie jest biblioteką przeznaczoną dla języka C (tylko C++), więc jeżeli chciałbyś użyć słownika, zapewne chciałbyś wykonać jego własną implementację. Poza tym słownik w tym przypadku jest rozwiązaniem nadmiarowym, a w może się i okazać, że jest rozwiązaniem złym i utrudniającym optymalizację.
Struktura, którą chcesz zbudować, to plansza do gry, a zatem to właśnie ona - plansza, powinna być opisana jako programistyczna struktura. Z tego co widzę, przechowywane wartości (pola tej planszy) są typu liczby całkowitej, nie ma więc potrzeby używać złożonej struktury do opisu samego pola (gdyby wartość była złożona, wtedy sprawa ma się inaczej). A zatem należy zdefiniować strukturę przechowującą niezbędne pola.
Kod: Zaznacz cały
struct Board
{
int *values;
int height;
int width;
};
typedef struct Board Board;
Należałoby napisać procedurę inicjalizującą taką planszę. W tej funkcji przypisujesz wysokość oraz szerokość zadanej planszy. Musisz również przypisać miejsce w pamięci dla tablicy przechowującej wartości pól tej planszy - miejsca potrzeba tyle, ile jest pól, razy miejsce potrzebne do przechowania jednego pola (czyli jednej liczby całkowitej). Czyli dla zadanej planszy
\(\displaystyle{ B}\), typu pola
\(\displaystyle{ P}\), wysokości
\(\displaystyle{ h}\) oraz szerokości
\(\displaystyle{ w}\), potrzebna pamięć planszy
\(\displaystyle{ s(B)}\) będzie wyrażona równaniem:
\(\displaystyle{
s(B) = w \cdot h \cdot s(P)
}\)
Ja dla bezpieczeństwa wypełniam planszę zerami. Nie trzeba tego robić, ale należy mieć świadomość, że odnoszenie się do niewypełnionego miejsca w pamięci to zły pomysł. Całość w języku C wygląda tak:
Kod: Zaznacz cały
void InitializeBoard(Board *b, int w, int h)
{
b->width = w;
b->height = h;
b->values = (int*)malloc(sizeof(int)*w*h);
for(int i = 0; i<w*h; i++)
b->values[i] = 0;
}
Definiuje również dwie proste metody - jedna pobiera wartość z planszy, druga zapisuje wartość na planszy. Obydwie metody mają STAŁY czas dostępu do pamięci. Aby obliczyć indeks
\(\displaystyle{ i}\) pola na wysokości
\(\displaystyle{ y}\) i szerokości
\(\displaystyle{ x}\) dla planszy o całkowitej wysokości
\(\displaystyle{ h}\) i całkowitej szerokości
\(\displaystyle{ w}\) posłużę się wzorem:
\(\displaystyle{
i = y \cdot w + x < h \cdot w
}\)
Kod: Zaznacz cały
int GetValue(Board b,int x, int y)
{
return b.values[y*b.width+x];
}
void SetValue(Board *b,int x, int y, int value)
{
b->values[y*b->width+x] = value;
}
Pomocniczo definiuję metodę drukującą elementy planszy.
Kod: Zaznacz cały
void PrintBoard(Board b)
{
for(int i = 0; i<b.height; i++)
{
for(int j = 0; j<b.width; j++)
printf("%d\t",b.values[i*b.width + j]);
printf("\n");
}
}
W końcu testuje działanie zaimplementowanych przeze mnie metod.
Kod: Zaznacz cały
int main()
{
Board *b;
b = (Board*)malloc(sizeof(Board*));
InitializeBoard(b,5,6);
PrintBoard(*b);
SetValue(b,3,4,5);
printf("------------------------\n");
PrintBoard(*b);
return 0;
}
Jeżeli chciałbyś przetestować to co napisałem, nie zapomnij o bibliotekach:
Model programu w którym "struktura planszy" wynika ze "struktury pola" jest modelem problematycznym, żeby nie powiedzieć złym - może z niego wynikać (jak u ciebie) na przykład liniowy czas dostępu do pamięci (co jest stanowczo niefektywne). Zauważyłem, że napisałeś, że zadana plansza nie musi być kwadratem. Mam podejrzenia (ze względu na mało precyzyjny język, którego używasz), że miałeś na myśli to, że plansza nie musi być prostokątem. Zaimplementowana przez mnie plansza kwadratem być nie musi, ale musi być prostokątem. Kiedy będziesz wykonywał własną implementację rozpocznij od definiowania planszy, a nie pola.