Probleme de informatica - enunturi si rezolvari

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;
}

21 nov 2024

Site-ul conține 884 de probleme rezolvate