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 (doi pași pe o direcție și un pas pe cealaltă direcție), 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 un traseu cu număr maxim de zone 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 traseucalmax.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 traseucalmax.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 traseucalmax.out vor fi zero.
oricare traseu valid al calului este considerat corect

Exemplu

traseucalmax.in

traseucalmax.out

1 4 0 8 0 
12 9 0 3 0 
5 2 13 10 7 
0 11 6 0 14

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 TraseuCalMax:

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

ifstream fin("traseucalmax.in");
ofstream fout("traseucalmax.out");

int n,m,is,js,ib,jb,a[11][11], tmax[11][11], dmax = 0,  ical, jcal, ifan, jfan;

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], ostream & out){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            if(a[i][j]<1)
                out << 0 << " ";
            else
                out << a[i][j] << " ";
        out << 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;
            if(i == n && j == m)
            {
                if(pas > dmax)
                {
                    dmax = pas;
                    for(int i =1 ; i <= n ; i ++)
                        for(int j =1 ; j <= m ; j ++)
                            tmax[i][j] = a[i][j];
                }
            }
            else
                for(int k = 0 ; k < 8; ++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);
    afis(tmax, fout);
    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 #2244 TraseuCalMax

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2244 TraseuCalMax 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 #2244 TraseuCalMax