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.

#include <bits/stdc++.h>
using namespace std;

const int di[] = {-1,1,2,2,1,-1,-2,-2};
const int dj[] = {2,2,1,-1,-2,-2,-1,1};

int n , m , x , y , a[205][205] , gata;

ifstream cin("saritura_calului1.in");
ofstream cout("saritura_calului1.out");

void afis()
{
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
            cout << a[i][j] << " ";
        cout<<'\n';
    }
    gata = 1;
}

int inside(int i , int j)
{
   return i >= 1 && i <= n && j >= 1 && j <= m;
}

int pozdisponibile(int i, int j)
{
    int cnt = 0;
    for(int d = 0 ; d < 8 ; d++)
    {
        int inou = i + di[d];
        int jnou = j + dj[d];
        if(inside(inou , jnou) && a[inou][jnou] == 0) cnt++;
     }
    return cnt;
}

void calgreedy(int i, int j, int pas)
{
    int val , mini = 9999999 ,ii,jj;
    if(!gata)
    {
        a[i][j] = pas;
        if(pas == n * m)  afis();
        else for(int d = 0 ; d < 8 ; d++)
        {
            int inou = i + di[d];
            int jnou = j + dj[d];
            if(inside(inou , jnou) && a[inou][jnou] == 0)
            {
               val = pozdisponibile(inou , jnou);
               if(val <= mini) mini = val , ii = inou , jj = jnou;
            }
        }
        if(mini != 99999) calgreedy(ii , jj , pas + 1);
        a[i][j] = 0;
    }
}

int main()
{
    cin>> n >> m >> x >> y;
    calgreedy(x , y , 1);
    return 0;
}