Probleme de informatica - enunturi si rezolvari

Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (10)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Harta unui oras este codificata ca o matrice nXm in care 0 reprezinta pozitie accesibila (strada) si -1 reprezinta pozitie inaccesibila (clarire, zid).
In pozitia ir,jr se afla Romeo, iar in pozitia ij,jj se afla Julieta. Romeo se poate deplasa pe pozitii cu laloarea 0, alaturate pe linii si coloane cu pozitia curenta, fara sa treaca de doua ori prin aceeasi pozitie.
Determinati si afisati cel mai scurt traseu pe care poate ajunge romeo la Julieta. Solutia se va afisa prin pasi marcari in matrice si ca sir de coordonate prin care trece Romeo.
Toate datele se citesc din fisierul rj.in, iar solutia se afiseaza in fisierul rj.out.
Exemplu:
Pentru datele de intrare:
5 7
-1 -1 0 -1 -1 -1 -1
-1 0 0 0 0 0 0
-1 0 -1 -1 -1 0 -1
-1 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1
2 2
3 6
solutia este:
-1 -1 0 -1 -1 -1 -1
-1 1 2 3 4 5 0
-1 0 -1 -1 -1 6 -1
-1 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1
2,2 2,3 2,4 2,5 2,6 3,6


#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[4]={-1,0,1,0};
const int dj[4]={0,1,0,-1};
int a[10][10], b[10][10],sol[100][3],x[100][3],n,m,pmin=100;
int ir,jr,ij,jj;
void citire()
{
	fin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			fin>>a[i][j];
	fin>>ir>>jr>>ij>>jj;	
}

int inside(int i, int j)
{
	return i>=1 && i<=n && j>=1 && j<=m;
}

void alege(int pas)
{
	if(pas<pmin)
	{
		pmin=pas;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				b[i][j]=a[i][j];
		for(int i=1;i<=pas;i++)
				{ sol[i][1]=x[i][1];
				  sol[i][2]=x[i][2];
				}  
	}
}

void afis()
{
	for (int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			fout<<b[i][j]<<" ";
        fout<<endl;		
	}
	for(int i=1;i<=pmin;i++)
		fout<<sol[i][1]<<","<<sol[i][2]<<"  ";
}

void back(int i,int j, int pas)
{
	int inou, jnou,k;
	if(i==ij && j==jj) alege(pas-1);
	else
		for(k=0;k<=3;k++)
		{
			inou=i+di[k];
			jnou=j+dj[k];
			if(inside(inou,jnou) && a[inou][jnou]==0 )
			{
				a[inou][jnou]=pas;
				x[pas][1]=inou;
				x[pas][2]=jnou;
				back(inou,jnou,pas+1);
				a[inou][jnou]=0;
			}
		}
}

int main()
{
	citire();
	a[ir][jr]=1;
	x[1][1]=ir;
	x[1][2]=jr;
	back(ir,jr,2);
	afis();
	fin.close();
	fout.close();
	return 0;
}

18 aug 2018
Site-ul conține 867 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian