Rezolvare completă PbInfo #384 Saritura_Calului1

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.

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

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

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 #384 Saritura_Calului1

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