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 integrală a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie.

Date de intrare

Programul citește de la tastatură 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

Programul afișează 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 ≤ 6
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• pentru fiecare dintre testele propuse, există soluție

Exemplu

Date de intrare

4 5 1 1

Date de ieșire

1 12 7 16 3 
6 17 2 11 8 
13 10 19 4 15 
18 5 14 9 20

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

int n , m , is , js , ib , jb , a[7][7] , cnt;

const int dic[] = {-2 , -1 , 1 , 2 ,  2 ,  1 , -1 , -2};
const int djc[] = { 1 ,  2 , 2 , 1 , -1 , -2 , -2 , -1};

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

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

void back(int i , int j , int pas)
{
    for(int d = 0 ; d < 8 ; d++)
    {
        int inou = i + dic[d];
        int jnou = j + djc[d];
        if(inside(inou , jnou) && a[inou][jnou] == 0)
        {
            a[inou][jnou] = pas;
            if(pas == n * m) 
            {
                afis();
                exit(0);
            }
            else back(inou , jnou , pas + 1);
            a[inou][jnou] = 0;
        }
    }
}
int main()
{
    cin >> n >> m;
    cin >> is >> js;
    a[is][js] = 1;
    back(is , js , 2);
    return 0;
}