Răspuns :
Salut am vrut sa iti scriu cand ai postat dar nu am avut timp.
Programul care l-am facut trebuie adaptat la cerintele exercitiului + mai trebuie sa reformulez prima conditie din backtrack(), dar am sa iti spun ce am facut pana acum:
const int x = rand, y = coloana;
int matrice[x][y] (plina cu valorea 0) //globala
functii: arata(), valideaza(r, c), backtrack(stop, r, c) //r = rand, c = coloana
arata() = arata matricea dupa ce e populata
valideaza(r, c) = returneaza TRUE daca matrice[r][c] == 0, FALSE daca matrice[r][c] != 0;
backtrack(stop, r, c) = stop este un index care se incrementeaza la fiecare reapelare.
in functia backtrack(stop, r, c) am facut conditii (doar if, NU AM FOLOSIT ELSE IF) pentru fiecare coordonate in care poate sari calul luate in ordinea acelor de ceas. Am facut asta scazand/adunand randul si coloana cu (1, 2) sau (2, 1). In momentul in care stop = x * y + 1 afisez matricea.
Am sa scriu si codul mai jos in cazul in care nu ai inteles ce am scris mai sus. Las comentarii in cod :)
(cum spuneam e doar o idee. programul trebuie adaptat pentru cerintele exercitiului)
#include <iostream>
using namespace std;
const int x = 4, y = 5; //x = randuri si y = coloane.
int tabla[x][y] = {}; //tabla sah
bool opreste = false; //variabila asta o folosesc in backtrack() pentru a arata matricea
void arata() //arat matricea
{
for(int r=0; r<x; r++)
{
for(int c=0; c<y; c++)
{
cout << tabla[r][c] << " ";
}
cout << endl;
}
}
bool valideaza(int r, int c) //returneaza ADEVARAT daca tabla[r][c] == 0, FALS daca nu
{
if(tabla[r][c] == 0)
{
return(true);
}
return(false);
}
void backtrack(int stop, int r, int c) //modific valorile din matrice
{
if((stop == x * y + 1) && (!opreste)) //arata matricea. opreste il folosesc pentru a nu afisa de mai multe ori
{ //aici trebuie sa fac niste modificari sa opresc mai eficient functia
arata();
opreste = true;
}
//de aici incep conditiile
if((r - 1 >= 0) && (c - 2 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop; //modific cifra din tabla[r][c]
backtrack(stop+1, r-1, c-2); //mut calul la coordonatele noi
tabla[r][c] = 0; //daca se blocheaza resetez pozitia tabla[r][c]
}
}
if((r - 2 >= 0) && (c - 1 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r-2, c-1);
tabla[r][c] = 0;
}
}
if((r - 2 >= 0) && (c + 1 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r-2, c+1);
tabla[r][c] = 0;
}
}
if((r - 1 >= 0) && (c + 2 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r-1, c+2);
tabla[r][c] = 0;
}
}
if((r + 1 < x) && (c + 2 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+1, c+2);
tabla[r][c] = 0;
}
}
if((r + 2 < x) && (c + 1 < y))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+2, c+1);
tabla[r][c] = 0;
}
}
if((r + 2 < x) && (c - 1 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+2, c-1);
tabla[r][c] = 0;
}
}
if((r + 1 < 4) && (c - 2 >= 0))
{
if(valideaza(r, c))
{
tabla[r][c] = stop;
backtrack(stop+1, r+1, c-2);
tabla[r][c] = 0;
}
}
}
int main()
{
backtrack(1, 0, 0);
return(0);
}
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!