# PBinfo #1332 – TraseuCal – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dă o tablă de șah formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. În zona de coordonate 1 1 se află un cal care se poate deplasa pe tablă în L, ca la șah, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați o modalitate prin care calul poate ajunge în zona de coordonate n m – unde se află o căpiță de fân.

Date de intrare
Fişierul de intrare traseucal.in conţine pe prima linie numerele n m, separate printr-un spațiu. Următoarele n linii conțin câte m valori, care descriu tabla: 0 corespunde unei zone libere, caracterul 1 corespunde unei zone ocupate de un obstacol.

Date de ieşire
Fişierul de ieşire traseucal.out va conţine n linii, pe fiecare linie fiind câte m numere, care descriu traseul calului, astfel: 


zonelor prin care nu va trece calul le corespund valoarea 0.
zonei în care se află inițial calul îi corespunde valoarea 1
următoarei zone din traseul calului îi corespunde valoarea 2
fiecărei zone din traseul calului îi corespunde o valoare număr natural semnificând la al câtelea pas ajunge calul în acea zonă.

Numerele de pe fiecare linie fișierului de ieșire sunt separate prin exact un spațiu.

Restricţii şi precizări

1 ≤ n,m ≤ 10
zona  în care se află calul și zona în care trebuie să ajungă sunt libere
dacă nu există nicio modalitate prin care calul ajunge la căpița de fân toate cele n*m numere din fișierul traseucal.out vor fi zero.
oricare traseu valid al calului este considerat corect

Exemplu:
traseucal.in

4 5
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
traseucal.out

1 4 0 0 0 
0 0 0 3 0 
0 2 5 0 0 
0 0 0 0 6

## Cod sursă C++

```cpp
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("traseucal.in");
ofstream fout("traseucal.out");
int n,m,is,js,ib,jb,a[11][11], nrsol = 0;
const int   di[]={2, 2, 1, 1,-1,-1,-2,-2}, 
            dj[]={1,-1, 2,-2, 2,-2, 1,-1};
void afis(int a[][11]){
	nrsol++;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)
			if(a[i][j]<1)
				fout << 0 << " ";
			else
				fout << a[i][j] << " ";
		fout << endl;
	}
}
void back(int i,int j, int pas)
{
        if(i>0 && i<=n && j>0 && j<=m && a[i][j]==0)
		{
			a[i][j] = pas;
            //afis(a);
            if(i==n && j==m)
				afis(a);
			else
				for(int k = 0 ; k < 8 && nrsol == 0 ; ++k)
					back(i+di[k], j+dj[k], pas+1);
			a[i][j] = 0;
		}
}
int main()
{
	fin >> n >> m;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
		{
			fin >> a[i][j];
			a[i][j] *= -1;
		}
    back(1, 1, 1);
	if(nrsol == 0)
		for(int i = 1 ; i <= n ; ++i)
        {
			for(int j = 1 ; j <= m ; ++j)
				fout << 0 << " ";
			fout << endl;
		}
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1332)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1332/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1332/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)