#include <iostream>
#include <iomanip>
#include <conio.h>
#include <fstream>
using namespace std;


int h[8][2] = {-2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1};
int daqua[50][50];
int x, y, m, n, sc;
fstream file;


//Hàm kiểm tra tọa độ và giới hạn bàn cờ
int ok(int u, int k)
{
	if (u >= 1 && u <= k)
		return 1;
	else
		return 0;
}

//hàm nhập kích thước bàn cờ
//nhập tọa độ quân Mã dầu tiên.
//Kiểm tra tọa độ hợp lý
void InPut()
{
	cout << "Nhap so hang (chieu dai M) cua ban co : ";
	cin >> m;
	cout << "Nhap so cot (chieu rong N) cua ban co : ";
	cin >> n;

	file << m << " x " << n << endl;
	do
	{
		cout << "Nhap toa do hang ban dau X cua con ma (1<=X<=M) : ";
		cin >> x;
	}
	while (!ok(x, m));//kiểm tra điều kiện hoành độ

	do
	{
		cout << "Nhap toa do cot ban dau Y cua con ma (1<=Y<=N) : ";
		cin >> y;
	}
	while (!ok(y, n));//kiểm tra điều kiện tung độ
	file << "(" << x << " , " << y << ")" << endl;
}

 //khởi tạo tổng số cách đi ban đầu là 0
// khởi tạo tại vị trí tọa độ xuất phát là nước 1.
void khoitao()
{
	sc = 0;
	daqua[x][y] = 1;
}

//hàm xuất bàn cờ, với c là số cách đi tức thời
void OutPut(int c)
{
	
	file << "-----------------------------------------------" << endl;
	file << "Cach thu " << c << " de con ma di het ban co : " << endl;

	//In bàn cờ và các nước đi của Mã
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		file << setw(4) << daqua[i][j];
		file << endl;
	}
}

//Hàm mã xuất tuần..
//hàm đệ quy.
//với u và v là tọa độ ban đầu của Quân mã.
void TimHanhTrinh(int u, int v, int c)
{
	
	int uu, vv; //tọa độ tức thời của Mã trên bàn cờ

	// điều kiện dừng với số nước đi của Mã bằng số ô trên bàn cờ..
	if (c == m * n)
	{
		sc++;
		OutPut(sc); //nếu thành thì xuất số cách và bàn cờ.
	}
	else
	{
		//Các nước đi của quân Mã.
		for (int i = 0; i <= 7; i++)
		{
			uu = u + h[i][0]; //tạo tọa độ cho mã từ tọa độ ban đầu u, v
			vv = v + h[i][1];
			if (ok(uu, m) && ok(vv, n))//kiểm tra tọa độ xác định không ra khỏi bàn cờ
				if (!daqua[uu][vv]) //nếu tại tọa độ đó mà Mã xác định. (#1) 
				{
					daqua[uu][vv] = c + 1;// tăng số nước đi cho Mã
					TimHanhTrinh(uu, vv, c + 1); //gọi lại chính hàm đệ quy để kiểm tra
					daqua[uu][vv] = 0; // đặt lại vị trí tọa độ là 0 để kiểm tra tiếp theo
				}
		}
	}
}


void main()
{
	file.open("Ma Di Tuan.txt", ios::out);
	InPut();
	khoitao();
	TimHanhTrinh(x, y, 1);//gọi hàm đệ quy.
	file << "-----------------------------------------------------------------\n-";
	file << "Vay, co' tong cong " << sc << " cach de con ma di het ban co!(^_^)";
	getch();
	file.close();
}