# PBinfo #384 – Saritura_Calului1 – Rezolvare C++

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

## Enunț

Cerinţa
Se consideră o tablă de şah cu n linii şi m coloane. La o poziţie dată se află un cal de şah, acesta putându-se deplasa pe tablă în modul specific acestei piese de şah (în L).

Să se determine o modalitate de parcurgere a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie. Parcurgerea constă într-o matrice cu n linii și m coloane, fiecare element al matricei având valoarea pasului la care se ajunge în acel element, sau 0, dacă nu s-a ajuns.

Date de intrare
Fișierul de intrare saritura_calului1.in conține numerele n şi m , apoi numere x y, reprezentând dimensiunile tablei (numărul de linii şi numărul de coloane) , respectiv coordonatele iniţiale ale calului (linie, coloana).

Date de ieşire
Fișierul de ieșire saritura_calului1.out va conține n linii cu câte m numere naturale cuprinse între 1 și n*m, separate prin exact un spațiu, reprezentând parcurgerea solicitată.

Restricţii şi precizări

1 ≤ n,m ≤ 100
1 ≤ istart ≤ n
1 ≤ jstart ≤ m
scorul obținut pe fiecare test este proporțional cu gradul de acoperire a tablei. Astfel, dacă tabla este acoperită în întregime, se acordă 100% din punctaj. Dacă tabla este acoperită în proporție de 70%, se acordă 70% din punctaj, etc.

Exemplul 1
saritura_calului1.in

4 5 1 1
saritura_calului1.out

1 12 7 16 3 
6 17 2 11 8 
13 10 19 4 15 
18 5 14 9 20
Explicație
Parcurgerea este completă, se va acorda 100% din punctaj.

Exemplul 2
saritura_calului1.in

4 5 1 1
saritura_calului1.out

1 12 7 16 3 
6 0 2 11 8 
13 10 0 4 15 
0 5 14 9 0
Explicație
Parcurgerea este parțială. S-au făcut 16 pași din 20, se va acorda 80% din punctaj.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("saritura_calului1.in");
ofstream fout("saritura_calului1.out");
int n, m, istart, jstart, a[105][105], best[105][105], bestpas;
const int di[]={2, 2,1, 1,-1,-1,-2,-2},
		  dj[]={1,-1,2,-2, 2,-2, 1,-1};
int x[8]={0,1,2,3,4,5,6,7};
int numar(int i,int j)
{
	int s = 0 , ii , jj;
	for(int k=0 ; k<8 ; ++k)
	{
		ii = i + di[x[k]], jj = j + dj[x[k]];
		if(ii>0 && ii <=n && jj>=1 && jj<=m && a[ii][jj]==0)
			s ++;
	}
	return s;
}
void greedy(int strict = 0)
{
	for(int i=1 ; i<=n ; ++i)
		for(int j=1 ; j<=m ; ++j)
			a[i][j] = 0;
	int pas = 1;
	int i = istart , j = jstart;
	while(1)
	{
		a[i][j]=pas;
		int min = 10, poz=-1;
		for(int k=0;k<8;++k)
		{
			int ii = i+di[x[k]], jj = j + dj[x[k]];
			if(ii>0 && ii <=n && jj>=1 && jj<=m && a[ii][jj]==0)
			{
				int nr = numar(ii,jj);
				if(strict){
					if(nr < min)
						min = nr, poz = k;
				}
				else
					if(nr <= min)
						min = nr, poz = k;
			}
		}
		if(min == 10)
			break;
		else
			i = i + di[poz], j = j + dj[poz], pas++;
	}
	if(pas > bestpas){
		bestpas = pas;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				best[i][j] = a[i][j];
	}
}
int main(){
	fin >> n >> m >> istart >> jstart;
	greedy();
	if(bestpas!=n*m)
		greedy(1);
	for(int i=1 ; i<=n ; ++i){
		for(int j=1 ; j<=m ; ++j)
			fout << best[i][j] << " ";
		fout << endl;
	}
	return 0;
}
```

## Resurse

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