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

traseucal.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema TraseuCal:

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

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1332 TraseuCal

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1332 TraseuCal de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1332 TraseuCal