Najcięższa droga w prostokątnej siatce.

Cześć,

Zdaje się, że mimo posiadania tu konta od iluś lat jest to mój pierwszy post, więc kolejne cześć na takie globalne przywitanie :D.

Mam taki algorytm do wymyślenia i napisania w C++, tylko jakoś nie wiem, jak się do tego zabrać...

Otóż jest sobie graf w postaci prostokątnej kraty, tzn. jest to siatka o wymiarach x na y, w której krawędzie istnieją tylko pionowe lub poziome, połączone jedynie z najbliższymi wierzchołkami. W praktyce wygląda to np tak

 
?-3-4-1-2-1
| | | | | |
4-7-8-1-4-5
| | | | | |
2-3-7-4-6-#

dla x=6 i y=3... Muszę znaleźć drogę z ? do # o największej wartości, jednocześnie najkrótszą, czyli mogę poruszać się tylko x razy w prawo i y razy w dół. Jeśli istnieje kilka dróg o tej samej największej wartości, to muszę znaleźć wszystkie.
Wiem więc, że potrzebuję jakiegoś rodzaju algorytmu który sprawdzi mi wszystkie możliwości, ale kompletnie nie wiem, co tak na prawdę powinien po kolei robić xD
Szczerze mówiąc nie potrafię dla tego grafu znaleźć nawet jakiejś nazwy, która powiedziałaby wyszukiwarce google więcej niż 'graf skierowany'...

Mam nadzieję że użyczycie mi swej mądrości i przybliżycie odrobinę sposób, w jaki można rozwiązać ten problem...

Wygląda jak programowanie dynamiczne.

1. Do każdego wierzchołka A można dojść tylko 2 drogami: z góry albo z lewej. Wystarczy więc sprawdzić którą bardziej się opłaca wybrać. Dla każdego wierzchołka trzymasz informację czy najlepsza droga jest z lewej czy z góry (albo z obu).
2. Lecisz pętlą po wszystkich punktach, od lewej do prawej, a wierszami z góry w dół. Dla każdego punktu liczysz to co w punkcie 1.

wartość każdego pola to a[x][y] = a[x][y] + max(a[x - 1][y], a[x][y - 1])

To, czego nie umiesz nazwać, to po prostu metryka miejska:
https://pl.wikipedia.org/wiki/Przestrze%C5%84_metryczna#Metryka_.E2.80.9Emiasto.E2.80.9D

Z modyfikacją, że u Ciebie drogi nie mają wagi.

Liczba wszystkich legalnych (najkrótszych) ścieżek z punktu A do punktu B to iloczyn niezbędnych skrętów poziomo i pionowo. Dla twojego przypadku to (x-1)*(y-1). Każdą ściężkę możesz zakodować za pomocą ciągu zer (skręt w prawo) i jedynek (skręt w dół). Np. idąc cały czas w prawo, a potem cały czas w dół masz 0000011.

Szukasz w necie jakiegoś algorytmu do wyszukiwania kolejnej permutacji, jeśli możesz używać w zadaniu, to używasz std::next_permutation
Odtwarzasz pętlą kolejnych ścieżek, zapamiętujesz najcięższą i gotowe.

// Pewnie jest coś ładniejszego, to tak na szybko.
// EDIT: Podejście dynamiczne jest lepsze. Użyj tego co masz wyżej napisane.

Dzięki wam za szybkie odpowiedzi, chyba powoli zaczynam rozumieć :D.

1. x - pozycje w szerz, y w dół. Zaczynasz od 1 wiersza. x1 to waga x1, x2 to waga x1+x2, waga x3 to waga x1 +x2 + x3, tak aż do końca wiersza
2. W kolejnym wierszu sprawdzasz co jest większe ( wartość komórki nad nią, czy tej po lewej ) i dodajesz do niej.
   W ten sposób masz w każdej komórce maksymalną drogę jaką do niej można dotrzeć ( a, że rozpatrujesz tylko lewo, góra to droga będzie najkrótsza ).
3. Potem dla ostatniego pola sprawdzasz które jest większe -> dla przypadku jak równe to kolejne na lewo - góra ( najprościej funkcję rekurencyjną, która wywołuje siebie aż do pierwszego pola gdy równe komórki )

W pierwszym punkcie w x2 to x2 + x1 natomiast x3 to suma wszystkich na lewo ( nie x1 + ( x1 + x2 ) + x3 ) - to może być nieścisłe