Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- using namespace std;
- char** alocaMatrice(int nrLin, int nrCol)
- {
- char **mat = new char*[nrLin];
- for(int i = 0;i < nrLin;i++)
- mat[i] = new char[nrCol];
- return mat;
- }
- void stergeMatrice(char** mat, int nrLin)
- {
- for(int i = 0;i < nrLin;i++)
- delete[] mat[i];
- delete[] mat;
- }
- // Functii care verifica daca cuvantul c poate fi plasat
- // in mat incepand de la pozitia (x,y) orizontal / vertical
- bool verifOriz(char **mat, int x, int y, char* c)
- {
- // Daca in pozitia corespunzatoare literei din c, in matrice
- // avem o alta litera si nu coincid nu putem pune cuvantul.
- for(int i = 0;c[i] != 0; i++)
- if(mat[x][y + i] != '-' && mat[x][y+i] != c[i]) return false;
- return true;
- }
- bool verifVert(char **mat, int x, int y, char* c)
- {
- for(int i = 0;c[i]!=0;i++)
- if(mat[x + i][y] != '-' && mat[x + i][y] != c[i]) return false;
- return true;
- }
- void bkt(char** cuv, int poz, int nrCuv, int nrLin, int nrCol, char **mat, char** sol)
- {
- if(poz == nrCuv) // indexarea fiind de la 0 inseamna ca am trecut prin toate cuvintele.
- {
- // salvam solutia in sol
- for(int i = 0;i<nrLin;i++)
- for(int j = 0;j<nrCol;j++)
- sol[i][j] = mat[i][j];
- return;
- }
- char **urm = alocaMatrice(nrLin,nrCuv); // in aceasta matrice vom efectua urmatoarea mutare.
- /// Afisare stadiu curent :
- /*cout << "ACUM :\n";
- for(int i = 0;i<nrLin;i++,cout << '\n')
- for(int j = 0;j<nrCol;j++)
- cout << mat[i][j] << ' ';
- cout << '\n' << '\n';*/
- for(int i = 0;i<nrLin;i++)
- for(int j = 0;j<nrCol;j++)
- urm[i][j] = mat[i][j];
- // Incercam sa plasam cuvantul cuv[poz] pe toate pozitiile orizontale posibile
- int len = strlen(cuv[poz]);
- for(int i = 0;i<nrLin;i++)
- for(int j = 0;j + len - 1 < nrCol;j++)
- if(verifOriz(mat,i,j,cuv[poz]))
- {
- // punem cuvantul in matricea urm
- for(int it = 0;it < len;it++)
- urm[i][j + it] = cuv[poz][it];
- bkt(cuv,poz+1,nrCuv,nrLin,nrCol, urm ,sol); // in urmatoarea mutare mat este urm.
- // stergem cuvantul din urm, ca sa putem face si alte mutari.
- for(int it = 0;it < len;it++)
- urm[i][j + it] = mat[i][j + it];
- }
- //cout << "CUV CURENT : " << cuv[poz] << '\n';
- // Procedam la fel dar acum pe verticala.
- for(int i = 0; i + len - 1 < nrLin;i++)
- for(int j = 0;j < nrCol; j++)
- if(verifVert(mat,i,j,cuv[poz]))
- {
- for(int it = 0;it < len;it++)
- urm[i + it][j] = cuv[poz][it];
- bkt(cuv, poz+1 , nrCuv, nrLin, nrCol, urm , sol);
- for(int it = 0;it < len;it++)
- urm[i+it][j] = mat[i + it][j];
- }
- // Nu uitam sa dealocam urm ca sa nu ne luam mare memory leak!!!
- stergeMatrice(urm, nrLin);
- }
- char** solutie(char **cuv, int nrCuv, int nrLin, int nrCol)
- {
- // In sol vom retine solutia finala si in mat vom simula mutarile
- char** mat = alocaMatrice(nrLin,nrCol);
- char** sol = alocaMatrice(nrLin,nrCol);
- for(int i = 0;i<nrLin;i++)
- for(int j = 0;j<nrCol;j++)
- mat[i][j] = sol[i][j] = '-';
- bkt(cuv, 0, nrCuv, nrLin, nrCol, mat, sol);
- stergeMatrice(mat,nrLin); // nu mai avem nevoie de ea deci o stergem.
- return sol;
- }
- int main()
- {
- // Apelarea functiei pentru a rezolva exemplul.
- int n = 6, m = 10;
- char **cuv = alocaMatrice(n,m);
- cuv[0] = "INFO";
- cuv[1] = "GREU";
- cuv[2] = "TEST";
- cuv[3] = "REN";
- cuv[4] = "JOC";
- cuv[5] = "FOC";
- /*for(int i = 0;i<n;i++)
- cout << cuv[i] << ' ' << strlen(cuv[i]) << '\n';*/
- int nrLin = 3, nrCol = 5;
- char **sol = solutie(cuv, n, nrLin, nrCol);
- for(int i = 0;i<nrLin;i++, cout << '\n')
- for(int j = 0;j<nrCol;j++)
- cout << sol[i][j] << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
