Problem sa zadatkom

Pitanja i problemi
1

Probao sam da resim zadatak “maksimalni bezbedni put” iz zbirke 2 na svaki moguci nacin, i josuvek dobija WA na nekim test primerima.
Ne smatram da je zadatak preterano tezak, pa zato pitam da li je mozda problem u tekstu ili test primerima.
Hvala unapred

(Petlja)

2

Zdravo,

Jel bi mogao da mi proslediš svoj kod kako bih mogao da vidim o čemu se radi?

Pozdrav,

David

3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector vi;
typedef vector vll;
typedef vector vvi;
typedef vector vvll;
typedef vector vpii;
#define run short O_O; cin >> O_O; while (O_O–)
#define all(v) v.begin(), v.end()
#define pb push_back
#define cintienull ios_base::sync_with_stdio(0); cin.tie(0);
#define mp make_pair
#define len length()
int n, m;
char v[20][20];
char kopi[20][20];
bool provera (int k, int l){
//printf(“pr za i%d j%d\n”,k,l);
//printf(“%d”, v[k-1][l]);
if (k > 0 && v[k - 1][l] == ‘0’)
return false;
if (k < n - 1 && v[k + 1][l] == ‘0’)
return false;
if (l > 0 && v[k][l - 1] == ‘0’)
return false;
if (l < m - 1 && v[k][l + 1] == ‘0’)
return false;
//printf(“tru\n”);
return true;

}
int maxsum;
void r(int i, int j, int sum)
{
//printf(“i = %d, j = %d, sum = %d\n”,i,j,sum);
if (j == m - 1){
//printf(“An\n”);
//ovaj deo nije spomenut u zadatku, ali jeste u test primeru
int zaposlrd1 = 0, zaposlrd2 = 0;
//if (i < n - 1){
for(int k = i; k < n; k++){
if(v[k][m - 1] == ‘!’)
break;
else
zaposlrd1 += v[k][m - 1] - ‘0’;
}
//}
//if (i > 0){
for(int k = i; k >= 0; k–){
if(v[k][m - 1] == ‘!’)
break;
else
zaposlrd2 += v[k][m - 1] - ‘0’;
}
//}
maxsum = max(sum + max(zaposlrd1, zaposlrd2) - (v[i][m-1] - ‘0’), maxsum);
return;
}
v[i][j] = ‘!’;
//printf(“v i j = %d\n”, v[i][j]);
if (i > 0 && v[i-1][j] != ‘!’){
//printf(“A\n”);
r(i - 1, j, sum + v[i - 1][j] - ‘0’);
//printf(“i-1\n”);
}
if (i < n - 1 && v[i+1][j] != ‘!’){
//px[i + 1][j] = v[i + 1][j] - ‘0’;
//printf(“aa\n”);
r(i + 1, j, sum + v[i + 1][j] - ‘0’);
//printf(“i+1\n”);
}
if (j > 0 && v[i][j-1] != ‘!’){
//px[i][j - 1] = v[i][j - 1] - ‘0’;
//printf(“Aaa\n”);
r(i, j - 1, sum + v[i][j - 1] - ‘0’);
//printf(“j-1\n”);
}
if (j < m - 1 &&v[i][j+1] != ‘!’){
//px[i][j + 1] = v[i][j + 1] - ‘0’;
//printf(“Aaaa\n”);
r(i, j + 1, sum + v[i][j + 1] - ‘0’);
//printf(“j+1\n”);
}
//printf(“aa\n”);
}
int main()
{
//cintienull
cin >> n >> m; //cin >> m >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
cin >> v[i][j];
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
if (!provera(i, j))
v[i][j] = ‘!’;
}

/*for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        cout << v[i][j] << ' ';
    }
    cout << '\n';
    }
cout << '\n';*/

 for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++){
        kopi[i][j] = v[i][j];
    }
int sum = 0;
maxsum = INT_MIN;
int maximum = INT_MIN;
//for(int i = 0; i < n; i++)
//    for(int j = 0; j < m; j++)
//        if(!provera(i,j) && v[i][j] != '0')
//            v[i][j] = '!';
bool ok = false;
for(int i = 0; i < n; i++){
    //printf("APSS\n");
    //printf("prover i = %d, j = %d\n",i , 0);
    if(kopi[i][0] != '!' && kopi[i][0] != '0'){
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
                v[i][j] = kopi[i][j];
        }
        //printf("prover i = %d, j = %d\n",i , 0);
        //printf("nasao: %d\n",kopi[i][0] - '0');
        maxsum = INT_MIN;
        sum = kopi[i][0] - '0';
        r(i, 0, sum);
        if (maxsum != INT_MIN)
            ok = true;
        maximum = max(maxsum, maximum);
    }
}
if (!ok)
    cout << "-1\n";
else
    cout << maximum << '\n';
return 0;

}

4

Mislim da je ipak najlakše da ti prosledim kod koji prolazi sve test primere, sa sve komentarima pa da vidiš kako bi se zadatak uradio. Evo koda:

// -- hide --
#include
#include

using namespace std;

// -- show --
// matrica i njene dimenzije
int bv, bk;
vector<vector> A;

// pomeraji koji odredjuju 4 susedna polja
int dv = {1, -1, 0, 0};
int dk = {0, 0, 1, -1};

const int MINA = 0;
const int NEBEZBEDNO = -1;
const int POSECENO = -2;

// provera da li se polje (v, k) nalazi unutar matrice
bool uMatrici(int v, int k) {
return 0 <= v && v < bv &&
0 <= k && k < bk;
}

// u matrici se obelezavaju sva nebezbedna polja (ona ciji su susedi mine)
void oznaciNebezbednaPolja() {
for (int v = 0; v < bv; v++)
for (int k = 0; k < bk; k++)
if (A[v][k] == MINA)
for (int i = 0; i < 4; i++) {
int vv = v + dv[i], kk = k + dk[i];
if (uMatrici(vv, kk) && A[vv][kk] != MINA)
A[vv][kk] = NEBEZBEDNO;
}
}

// put sa najvecim zbirom od polja (v, k) do donjeg reda matrice
int maksPut(int v, int k) {
int maks = -1;
if (v == bv-1)
maks = A[v][k];

int tmp = A[v][k];
A[v][k] = POSECENO;
for (int i = 0; i < 4; i++) {
int vv = v + dv[i], kk = k + dk[i];
if (uMatrici(vv, kk) && A[vv][kk] != POSECENO && A[vv][kk] != NEBEZBEDNO) {
int put = maksPut(vv, kk);
if (put != -1)
maks = max(maks, put + tmp);
}
}
A[v][k] = tmp;
return maks;
}

int maksBezbedniPut() {
// oznacavamo nebezbedna polja
oznaciNebezbednaPolja();
// najveci zbir koji se moze prikupiti
int maks = -1;
// posebno pokrecemo pretragu iz svakog polja u prvom redu matrice
for (int k = 0; k < bk; k++) {
if (A[0][k] != MINA && A[0][k] != NEBEZBEDNO) {
int put = maksPut(0, k);
if (put != -1)
maks = max(maks, put);
}
}
return maks;
}
// -- hide --

// ucitavanje matrice sa standardnog ulaza
void citajMatricu() {
cin >> bv >> bk;
A.resize(bv, vector(bk));
for (int v = 0; v < bv; v++)
for (int k = 0; k < bk; k++)
cin >> A[v][k];
}

int main() {
citajMatricu();
// ispisujemo najpovoljniji put
cout << maksBezbedniPut() << endl;

return 0;
}

5

hvala puno : )

1 Like
6

Nema na čemu, nadam se da ti je pomoglo :slight_smile:

1 Like