Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Air Moldova

Rambursare anticipata credit OTP

placa de baza asus p8h61

Forza Horizon 3 xbox one
 Stick usb nu apare in explorer

A murit Anca Pop

Problema recunoastere Intel Optan...

Diacritice in programe scrise in ...
 Bagaj de cala deteriorat blue air...

Programul RABLA la Electrocasnice

Mutant Year Zero: Road to Eden

Varg Vikernes si familia traditio...
 Probleme Windows 10, mai ales in ...

Taba border - Israel taxa iesire

centrala hidro sub apa marii

Diversiunea Ion Iliescu - "Le...
 

Backtracking c++

- - - - -
  • Please log in to reply
7 replies to this topic

#1
AlinToncea00

AlinToncea00

    Junior

  • Grup: Junior Members
  • Posts: 2
  • Înscris: 12.03.2018
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);
}



#2
gmartau

gmartau

    Junior

  • Grup: Members
  • Posts: 313
  • Înscris: 30.04.2008
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.

#3
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 20,233
  • Înscris: 10.08.2005
Matricea este formata din elemente
Elementele au proprietati, pe care tu le-ai etichetat intr-un anumit mod.

#4
AlinToncea00

AlinToncea00

    Junior

  • Grup: Junior Members
  • Posts: 2
  • Înscris: 12.03.2018

View Postgmartau, on 12 martie 2018 - 19:37, said:

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.
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

#5
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 20,233
  • Înscris: 10.08.2005
Transforma matricea intr-un graf

#6
WinstonMontana

WinstonMontana

    Active Member

  • Grup: Members
  • Posts: 1,913
  • Înscris: 20.02.2018
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.


#7
pexCom

pexCom

    Member

  • Grup: Members
  • Posts: 847
  • Înscris: 15.01.2014
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.


#8
dani.user

dani.user

    Guru Member

  • Grup: Moderators
  • Posts: 24,196
  • Înscris: 24.02.2007
Ce inseamna bordare?

Anunturi


0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate