x - Load data from default.txt file
y - Load data from any .txt file
z - Load data manually
p - Print loaded data
g - Generate random data to default.txt
s - Solve and display the result
l - Solve in a loop, show the time
d - Perform the default test, results in results.txt
c - Perform a custom test, results in results.txt
h - Display this help message
q - Exit
Plik zawiera w pierwszej linii jedną liczbę całkowitą, rozmiar mapy N
W nastepnych N liniach znajduje się po N liczb całkowitych z zakresu 0-M, elementów mapy
Przykład zawartości pliku:
3
1 0 5
5 4 3
2 6 2
Dla danego momentu czasu t sprawdzanie metodą "przejścia wzdłuż prawej ściany" czy przejście jest możliwe.
Na pewno nie da się przepłynąć przez mapę w czasie krótszym niż wartość wysokości pierwszego i ostatniego pola, więc sprawdzanie zaczyna się od maksimum z tych wartości.
Następnie sprawdzane są coraz większe (przy każdej iteracji 1.5x większe niż poprzednie) wartości czasu t aż do osiągnięcia takiej, w której przepłynięcie jest możliwe.
Gdy znana jest taka wartość, binarnie przeszukujemy przestrzeń pomiędzy nią a największą dotychczas znalezioną wartością czasu, w której przejście nie jest możliwe.
Przewidywana pesymistyczna złożoność czasowa to O(N^2*log(M)).
Złożoność pamięciowa to O(N^2).
main.cpp - wywołuje główną metodę klasy Tide
Tide.cpp, Tide.h - służy komunikacji programu z użytkownikiem i wczytywaniu danych
Solution.cpp, Solution.h - implementacja algorytmu
Timer.cpp, Timer.h - prosta klasa służąca do pomiaru czasu
Zakres wartości N: 1 - 10^9 (testowanie jest realne dla N <= 10^4)
Zakres wartości M: 1 - 10^9
Generator generuje mapę NxN wartości pseudolosowych z zakresu 0-M