Znam da ovo nije direktno povezano s petljom i zadacima na petlji, ali čisto sam hteo da se raspitam ako je neko na ovom forumu rešio zadatak Minimal Grid Path iz CSES zbirke zadataka? Koliko vidim - zadatak je nerešiv pomoću DP tehnike (a u tom delu zbirke je), ali verovatno se varam pa samim tim i postavljam pitanje da ako neko ima kod za taj zadatak, bio bih mu zahvalan da ga podeli
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf = 2000000000000;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
ll n;
string red;
cin >> n;
vector<vector>polja(n, vector(n));
for(ll i = 0; i < n; i++){
cin >> red;
for(ll j = 0; j < n; j++){
polja[i][j] = red[j];
}
}
string resenje = “”; // ovde cemo cuvati resenje
vector<pair<ll, ll>>trenutnapolja; // kako cemo prolaziti kroz tabelu BFS-om ovde cemo cuvati polja koja su trenutno u opticaju
trenutnapolja.push_back(make_pair(0, 0));
for(ll i = 0; i < (2 * n - 1); i++){
char najmanji = ‘}’; // veca ascii vrednost od svih slova
for(auto polje : trenutnapolja){
ll y = polje.first;
ll x = polje.second;
najmanji = min(najmanji, polja[y]); // nalazimo najmanje slovo koje mozemo da dodamo u resenje
}
resenje += najmanji; // dodajemo najmanje slovo na resenje
vector<pair<ll, ll>>sledecapolja;
for(auto polje : trenutnapolja){
ll y = polje.first;
ll x = polje.second;
if(polja[y] == najmanji){
if(y < (n - 1)){
sledecapolja.push_back(make_pair(y + 1, x)); // u koja sve polja mozemo da dodjemo u sledecem potezu ako sad dodamo najmanje slovo na resenje
}
if(x < (n - 1)){
sledecapolja.push_back(make_pair(y, x + 1));
}
}
}
sort(sledecapolja.begin(), sledecapolja.end());
sledecapolja.erase(unique(sledecapolja.begin(), sledecapolja.end()), sledecapolja.end()); // uklonimo duplikate
trenutnapolja = sledecapolja;
}
cout << resenje << endl;
}