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 va ajunge la căpița de fân toate cele
n*m
numere din fișierultraseucal.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
#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; }