Backtracking c++

Salut !
Lucrez la un proiect pentru scoala legat de backtracking in plan . Am primit o problema pe care nu reusesc sa o termin .
Cerinta e urmatoarea :
Un iepure parcurge o matrice formata din litere incepand din coltul sus stanga pana in coltul dreapta jos . Matricea e formata din urmatoarele litere cu urmatoarea semnifcatie specifica pentru fiecare :
A - zona libera de trecere
Z - zona prin care nu se poate trece
L - zona prin care nu se poate trece
M , V - zone prin care se poate trece doar daca nu se afla in imediata apropiere unei litere L
Iepurele parcurge matricea pe directiile N S V E.
Cerinta e sa afisez toate traseele pe care le parcurge iepurele + numarul de litere M si V pe care le parcurge intr-un traseu .
Problema pe care o are programul meu cred ca e in subprogramul de backtracking pentru ca nu afiseaza nimic.
Acesta e codul scris de mine :

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("iepure.in");
ofstream g("iepure.out");
struct p
{
	int c,d;
} st[101];
char a[101][101];
int n,m,b[101][101],k;
int valid (int x,int y)
{
	if(a[x][y]=='Z' || a[x][y]=='L')
		return 0;
	if(a[x][y]=='M' || a[x][y]=='V')
		if(a[x+1][y]=='L' || a[x-1][y]=='L' || a[x][y+1]=='L' || a[x][y-1]=='L')
			return 0;
		else
			return 1;
	if(a[x][y]=='D')
		return 0;
	return 1;
}
void tipar(int niv)
{
	int i,mo=0,va=0;
	for(i=1; i<=niv; i++)
	{
		g<<st[i].c<<' '<<st[i].d;
		if(a[st[i].c][st[i].d] == 'M')
			mo++;
		if(a[st[i].c][st[i].d] == 'V')
			va++;
		g<<endl;
	}
	g<<mo<<' '<<va;
}
void bordare(int n, int m)
{
	int i,j;
	for(i=0; i<=n+1; i++)
	{
		a[i][0]='D';
		a[i][n+1]='D';
	}
	for(j=0; j<=m+1; j++)
	{
		a[0][j]='D';
		a[m+1][j]='D';
	}
}
void bk(int x,int y,int niv)
{
	st[niv].c=x;
	st[niv].d=y;
	if(niv!=1)
		b[x][y]=1;
	if(valid(x,y)==1 && st[niv].c==n && st[niv].d==m)
			tipar(niv);
		else if(b[x][y]==0 || niv==1)
		{
			bk(x+1,y,niv+1);
			bk(x-1,y,niv+1);
			bk(x,y+1,niv+1);
			bk(x,y-1,niv+1);
		}
	b[x][y]=0;
}
int main()
{
	f>>n>>m;
	int i,j;
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			f>>a[i][j];
	bordare(n,m);
	bk(1,1,1);
}

Daca ai priceput algoritmul, de ce nu rulezi programul pas cu pas sa vezi unde nu functioneaza cum te astepti? Eu stiu ca asa se face depanare, sau mai nou se face pe forum? Nu te supara dar asa vei fi mult mai castigat.

Matricea este formata din elemente
Elementele au proprietati, pe care tu le-ai etichetat intr-un anumit mod.

gmartau, on 12 martie 2018 - 19:37, said:

Am facut asta si am si mentionat ca problema e in subprogramul de backtracking , dar nu gasesc nicio solutie de a-l scrie in alt mod si tocmai de aia va ceream ajutorul

Transforma matricea intr-un graf

ah, scoala romaneasca vesnica cu acelasi  limbaj de lemn si ce acelai tip de probleme:  "un iepure sarea intr-o matrice....". In primul rand redenumeste si tu variabilele alea sa aiba un  nume care sa explice succint ce ar trebui sa stocheze iar numele  algoritmului principal de ce nu-l de numeste backtracking ci "bk".
Nimeni nu o sa-ti stea sa se uite pe acest program chiar si cei care stiu backtraking, dupa o zi de munca ,daca programul este scris intr-un "limbaj de lemn".

Apoi o alta chestie care de fapt tine te baga in ceata este formularea problemei insasi: "un iepure sarea intr-o matrice....".Desi nu-ti dai seama, insusi formularea problemei in limbaj de lemn
este  o problema pt ca al tau creier a fost obisnuit ca intre simbolul si conceptul abstract "matrice" si animalul iepure nu exista nici o legatura.

De aceea problemele in lumea reala care se rezolva prin backtraking  au o formulare realista si dupa ce ai citit enuntul realist al unei astfel de probleme si stiind si tehnica atunci ai deja in cap 2/3 din rezolvare doar dupa ce ai citit problema formulata in sens realist.

Edited by WinstonMontana, 12 March 2018 - 20:02.

Pentru inceput, faci ceva destul de dubios cu citirea matricii din fisier si apoi in functia bordare.

Citesti elementele matricii incepand cu a doua pozitie si pe linie si pe coloana, asteptandu-te (presupun) ca elementele de pe frontiera sa ramana goale. Presupun ca ai 99 linii si coloane in fisier, pentru ca matricea a ai initializat-o cu 101x101 elemente, ca sa iti ramana pentru 'D'-urile pe frontiera.

In realitate, o sa iti puna D-uri la fiecare al 101-lea element, deci cam peste tot prin matrice, nu doar la frontiera.
Mai studiaza ce inseamna matrice in C/C++, care e legatura intre ea si pointeri, si ce inseamna sa accesezi/scrii intr-un element al ei.

O solutie destul de simpla ar fi sa scrii direct matricea in fisier cu tot cu D-urile de pe frontiera, si sa o citesti cap-coada in program (renunti la functia bordare).

Pana aici m-am uitat, posibil sa mai fie erori si la backtracking.

Edited by pexCom, 13 March 2018 - 14:29.

Ce inseamna bordare?