Jeszcze dopowiedziałbym, kilka rzeczy o tym zadaniu.
Oczywiście to co zrobiliście było najłatwiejsze i wzorcowe, ale można podejśc do tego innymi sposobami.
Po 1 traktujesz całośc jako graf, gdzie wierzchołki w polach i,j. Masz ich dokładnie N*M. Puszczasz Dijkstrę równolegle(wrzucasz wszystkie wierzcholki z 1 kolumny, które mają wartosć 0 na seta, i robisz Dijkstrę, gdzie krawędzie masz 3 opcje:
1 - krawędź i, j+1 ma wagę 0.
2 - krawędź i-1, j ma wagę 1
3 - krawędź i+1, j ma wagę 1
I idziesz sobie normalnie Dijkstrą i zauważ, że nie masz krawędzi i, j-1, bo nie możesz się cofać! Kończysz, gdy dojdziesz na pole w ostatniej kolumnie. Takie rozwiązanie ma O(N*M * lg(N*M)), czy coś koło tego, i przechodzi na setkę, napisałem coś takiego, gdybym źle opisał.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct Element_seta
{
int wartosc;
int y;
int x;
bool operator < (const Element_seta &element_seta) const
{
if (wartosc == element_seta.wartosc)
{
if (y == element_seta.y)
return x < element_seta.x;
return y < element_seta.y;
}
return wartosc < element_seta.wartosc;
}
};
int n = 0, m = 0, wczytana_liczba = 0;
vector<vector<int>> plansza;
vector<vector<int>> dp;
set<Element_seta> S;
int main()
{
// O(N*M * lg(N*M))
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
plansza.push_back({});
dp.push_back({});
for (int j = 0; j < m; ++j)
{
cin >> wczytana_liczba;
plansza[i].push_back(wczytana_liczba);
dp[i].push_back(-1);
}
}
for (int i = 0; i < n; ++i)
{
// Dodajemy wierzcholki startowe na seta.
if (plansza[i][0] == 0)
{
S.insert({0,i,0});
dp[i][0] = 0;
}
}
while(!S.empty())
{
Element_seta spr = *S.begin();
if (spr.x == m-1)
{
cout << spr.wartosc << '\n';
return 0;
}
S.erase(spr);
// Krawedzie o wadze 0.
if (spr.x + 1 < m)
{
if (plansza[spr.y][spr.x+1] == 0)
{
if (dp[spr.y][spr.x+1] == -1 || spr.wartosc < dp[spr.y][spr.x+1])
{
auto it = S.find({dp[spr.y][spr.x+1],spr.y,spr.x+1});
if (it != S.end())
S.erase(*it);
dp[spr.y][spr.x+1] = spr.wartosc;
S.insert({spr.wartosc,spr.y,spr.x+1});
}
}
}
// Krawedzie o wadze 1
if (spr.y + 1 < n)
{
if (plansza[spr.y+1][spr.x] == 0)
{
if (dp[spr.y+1][spr.x] == -1 || spr.wartosc + 1 < dp[spr.y+1][spr.x])
{
auto it = S.find({dp[spr.y+1][spr.x],spr.y+1,spr.x});
if (it != S.end())
S.erase(*it);
dp[spr.y+1][spr.x] = spr.wartosc + 1;
S.insert({spr.wartosc + 1,spr.y+1,spr.x});
}
}
}
if (spr.y - 1 >= 0)
{
if (plansza[spr.y-1][spr.x] == 0)
{
if (dp[spr.y-1][spr.x] == -1 || spr.wartosc + 1 < dp[spr.y-1][spr.x])
{
auto it = S.find({dp[spr.y-1][spr.x],spr.y-1,spr.x});
if (it != S.end())
S.erase(*it);
dp[spr.y-1][spr.x] = spr.wartosc + 1;
S.insert({spr.wartosc + 1,spr.y - 1,spr.x});
}
}
}
}
cout << "NIE" << '\n';
return 0;
}
2 - zauważ, że w tym przypadku masz graf o krawędziach z wagami 1 oraz 0, więc możesz na deque zoptymalizować Dijkstrę, korzystając z tego, że wartości na deque nie będą różnić się o więcej niż 1! W zależności od tego czy przetwarzasz o wadze 0 czy o wadze 1, to dodajesz na początek / koniec deque. Usuniemy loga - O(N*M) - też wzorcówka
Tu masz kod:
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
struct Element_seta
{
int wartosc;
int y;
int x;
bool operator < (const Element_seta &element_seta) const
{
if (wartosc == element_seta.wartosc)
{
if (y == element_seta.y)
return x < element_seta.x;
return y < element_seta.y;
}
return wartosc < element_seta.wartosc;
}
};
int n = 0, m = 0, wczytana_liczba = 0;
vector<vector<int>> plansza;
vector<vector<int>> dp;
deque<Element_seta> S;
vector<vector<bool>> czy_sprawdzilismy;
int main()
{
// O(N*M)
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
plansza.push_back({});
dp.push_back({});
czy_sprawdzilismy.push_back({});
for (int j = 0; j < m; ++j)
{
cin >> wczytana_liczba;
plansza[i].push_back(wczytana_liczba);
dp[i].push_back(-1);
czy_sprawdzilismy[i].push_back(false);
}
}
for (int i = 0; i < n; ++i)
{
// Dodajemy wierzcholki startowe na seta.
if (plansza[i][0] == 0)
{
S.push_back({0,i,0});
dp[i][0] = 0;
}
}
while(!S.empty())
{
Element_seta spr = S.front();
S.pop_front();
if (czy_sprawdzilismy[spr.y][spr.x] == true)
continue;
if (spr.x == m-1)
{
cout << spr.wartosc << '\n';
return 0;
}
// Krawedzie o wadze 0.
if (spr.x + 1 < m)
{
if (plansza[spr.y][spr.x+1] == 0)
{
if (dp[spr.y][spr.x+1] == -1 || spr.wartosc < dp[spr.y][spr.x+1])
{
dp[spr.y][spr.x+1] = spr.wartosc;
S.push_front({spr.wartosc,spr.y,spr.x+1});
}
}
}
// Krawedzie o wadze 1
if (spr.y + 1 < n)
{
if (plansza[spr.y+1][spr.x] == 0)
{
if (dp[spr.y+1][spr.x] == -1 || spr.wartosc + 1 < dp[spr.y+1][spr.x])
{
dp[spr.y+1][spr.x] = spr.wartosc + 1;
S.push_back({spr.wartosc + 1,spr.y+1,spr.x});
}
}
}
if (spr.y - 1 >= 0)
{
if (plansza[spr.y-1][spr.x] == 0)
{
if (dp[spr.y-1][spr.x] == -1 || spr.wartosc + 1 < dp[spr.y-1][spr.x])
{
dp[spr.y-1][spr.x] = spr.wartosc + 1;
S.push_back({spr.wartosc + 1,spr.y - 1,spr.x});
}
}
}
}
cout << "NIE" << '\n';
return 0;
}
3 - Można napisać prostego BFS-a, gdzie robisz 2 rzeczy. Po 1 najpierw dodajesz na vector wierzcholki z 1 kolumny, i rozlewasz się każdym do przodu(w tym samym wierszu) i dodajesz je na vector. Potem po dodaniu iterujesz się po tym vectorze, i dodajesz na vector te do góry / dół z wagą o 1 większą. I tak w kółko - O(N*M) - wzorcówka.
Przypomniałem sobie o takim zdaniu z OIG-a: https://szkopul.edu.pl/problemset/problem/OwOeE32S_q-mlnooF5Od_eoy/site/?key=statement wchodzi na ten sam trik.
