👤
a fost răspuns

Buna ziua, nu pot rezolva problema monkey din campion.edu.ro am incercat deja de mult timp si nu se primeste, dacda ma poate cineva ajuta:

Monkey este un joc pentru un singur jucator, care se joaca pe o tabla dreptunghiulara impartita casute care formeaza R linii si C coloane. In fiecare casuta a tablei se afla o litera mare a alfabetului englez (de la A la Z).
Jucatorul are un jeton pe care este desenata o maimuta. Inainte de inceperea jocului maimuta va fi plasata in coltul din stanga sus al tablei (prima linie, prima coloana).
La o mutare, jucatorul poate plasa maimuta pe una dintre pozitiile adiacente pozitiei sale curente (adica pe o pozitie invecinata, aflata sus, jos, in stanga sau in dreapta). Singura restrictie este ca maimuta nu poate fi asezata de doua ori peste o aceeasi litera.
Scopul jocului este de a face cât mai multe mutari.

Cerinta

Scrieti un program care sa determine numarul maxim de pozitii pe care le poate "vizita" maimuta intr-un singur joc.

Date de intrare

Pe prima linie a fisierului de intrare monkey.in se afla doua numere naturale R si C separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale tablei de joc. Pe fiecare dintre urmatoarele R linii se afla C litere, care reprezinta literele aflate pe tabla pe linia respectiva.

Date de iesire

Fisierul de iesire monkey.out contine o singura linie pe care se afla numarul maxim de pozitii de pe tabla de joc ce au putut fi vizitate de maimuta.

Restrictii

1 <= R, C <= 20

Ajutati-ma va rog

Răspuns :

Emil1234
Mi-am facut pana la urma putin timp pentru a ma uita peste problema.
Aici este solutia pentru 100 puncte pe campion:


#include <iostream>

#include <fstream>

int l,lmax,verif_trecere[26];

using namespace std;


void rezolvare(int x,int y, char s[21][21],int R, int C){

    if(verif_trecere[s[x][y] - 'A'] || x < 0 || y < 0 || x >= R || y >= C) return;

    verif_trecere[s[x][y] - 'A'] = 1;

    l++;

    if(l>lmax) lmax = l;

    rezolvare(x-1,y,s,R,C);

    rezolvare(x+1,y,s,R,C);

    rezolvare(x,y-1,s,R,C);

    rezolvare(x,y+1,s,R,C);

    verif_trecere[s[x][y] - 'A'] = 0;

    l--;

}


int main()

{

    int R,C;

    char s[21][21];

    ifstream fin("monkey.in");

    ofstream fout("monkey.out");

    fin>>R>>C;

    for(int i=0;i<R;i++)

        for(int j=0;j<C;j++)

            fin>>s[i][j];

    rezolvare(0,0,s,R,C);

    fout<<lmax;

    fin.close();

    fout.close();

    return 0;

}

Bafta in continuare la probleme!