TraseuCal

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ș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 
#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;
}
%d bloggers like this: