// DuongTanThanh.Net
// Sdt: 0169.736.4746
// Yahoo: khongthengungchat

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define max 100
#define fo "madituan.out"

FILE *f;
int X[8]={-2,-2,-1,1,2,2,1,-1},
    Y[8]={-1,1,2,2,1,-1,-2,-2},
    sodong, socot, dd[max][max],
    csdong, cscot, sonuocdi;

typedef struct vitri{
   int bac, csd, csc;
};
typedef struct node{
   vitri info;
   node *next;
};
typedef struct list{
   node *pHead, *pTail;
};

void input(){
   printf("Nhap so dong: ");scanf("%d",&sodong);
   printf("Nhap so cot: ");scanf("%d",&socot);
   printf("Nhap toa do cua quan Ma:\n");
   printf("x = ");scanf("%d",&csdong);
   printf("y = ");scanf("%d",&cscot);
   for (int i=0; i<sodong; i++)
   for (int j=0; j<socot;  j++)
      dd[i][j]=0;
   sonuocdi = 1;
   dd[csdong][cscot] = 1;
}

int in(int i, int j){
   if ((0<=i)&&(i<sodong)&&(0<=j)&&(j<socot))
      return 1;
   return 0;
}

void push(list &l, node *p){
   if (l.pHead==NULL)
      l.pHead=l.pTail=p;
   else{
      p->next=l.pHead;
      l.pHead=p;
   }
}

node *getnode (int bac, int csd, int csc){
   vitri o;
   o.bac = bac;
   o.csd = csd;
   o.csc = csc;
   node *p= new node;
   p->info = o;
   p->next = NULL;
   return p;
}

int bac (int x, int y){
   int b=0;
   for (int i=0; i<8; i++)
      if (in(x+X[i], y+Y[i])&&(dd[x+X[i]][y+Y[i]]==0))
         b++;
   return (b);
}

void interchange(list &l){
   node *p=l.pHead;
   while (p != NULL){
      node *q=p->next;
      while (q != NULL){
            if (q->info.bac < p->info.bac){
            vitri temp=q->info;
            q->info = p->info;
            p->info = temp;
            }
            q = q->next;
      }
      p = p->next;
   }
}

list getlist(int csd, int csc){
   list l;
   l.pHead=l.pTail=NULL;
   for (int i=0; i<8; i++)
      if (in(csd+X[i], csc+Y[i])&&(dd[csd+X[i]][csc+Y[i]]==0)){
         node *p = getnode(bac(csd+X[i], csc+Y[i]), csd+X[i], csc+Y[i]);
         push(l, p);
      }
   interchange(l);
   return l;
}

void output(int kq[max][max]){
   f=fopen(fo,"w");
   for (int i=0; i<sodong; i++){
      for (int j=0; j<socot; j++){
         fprintf(f,"%4d",kq[i][j]);
      }
      fprintf(f,"\n");
   }
   fclose(f);
   printf("Xem ket qua o file MaDiTuan.Out");
   getch();
   exit(1);
}

void doing(int csd, int csc){
   list l = getlist(csd, csc);
   while (l.pHead!=NULL){
      sonuocdi++;
      dd[l.pHead->info.csd][l.pHead->info.csc] = sonuocdi;
      doing(l.pHead->info.csd, l.pHead->info.csc);
      dd[l.pHead->info.csd][l.pHead->info.csc] = 0;
      sonuocdi--;
      node *p = l.pHead;
      l.pHead = p->next;
      delete(p);
   }
   if (sonuocdi == sodong*socot)
      output(dd);
}

void main(){
   clrscr();
   input();
   doing(csdong, cscot);
   printf("Khong tim thay duong di nao thoa man bai toan MA DI TUAN");
   getch();
}

// DuongTanThanh.Net
// Sdt: 0169.736.4746
// Yahoo: khongthengungchat

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define max 100
#define fo "madituan.out"

FILE *f;
int X[8]={-2,-2,-1,1,2,2,1,-1},
    Y[8]={-1,1,2,2,1,-1,-2,-2},
    sodong, socot, dd[max][max],
    csdong, cscot, sonuocdi;

void input(){
   printf("Nhap so dong: ");scanf("%d",&sodong);
   printf("Nhap so cot: ");scanf("%d",&socot);
   printf("Nhap toa do cua quan Ma:\n");
   printf("x = ");scanf("%d",&csdong);
   printf("y = ");scanf("%d",&cscot);
   for (int i=0; i<sodong; i++)
   for (int j=0; j<socot;  j++)
      dd[i][j]=0;
   sonuocdi = 1;
   dd[csdong][cscot] = 1;
}

int in(int i, int j){
   if ((0<=i)&&(i<sodong)&&(0<=j)&&(j<socot))
      return 1;
   return 0;
}

int bac (int x, int y){
   int b=0;
   for (int i=0; i<8; i++)
      if (in(x+X[i], y+Y[i])&&(dd[x+X[i]][y+Y[i]]==0))
         b++;
   return (b);
}

void swap(int list[8][3], int x, int y){
   int temp;
   for (int i=0; i<3; i++){
      temp=list[x][i];
      list[x][i]=list[y][i];
      list[y][i]=temp;
   }
}

void bubble(int list[8][3], int spt){
   for (int i=0; i<spt-1; i++)
      for (int j=spt-1; j>i; j--)
         if (list[j][0]<list[j-1][0])
            swap(list,j,j-1);
}

void create(int x, int y, int list[8][3], int &spt){
   spt=0;
   for (int i=0; i<8; i++)
      if (in(x+X[i], y+Y[i])&&(dd[x+X[i]][y+Y[i]]==0)){
         list[spt][0]= bac(x+X[i], y+Y[i]);
         list[spt][1]= x+X[i];
         list[spt][2]= y+Y[i];
         spt++;
      }
   bubble(list, spt);
}

void output(int kq[max][max]){
   f=fopen(fo,"w");
   for (int i=0; i<sodong; i++){
      for (int j=0; j<socot; j++){
         fprintf(f,"%4d",kq[i][j]);
      }
      fprintf(f,"\n");
   }
   fclose(f);
   printf("Xem ket qua o file MaDiTuan.Out");
   getch();
   exit(1);
}

void doing(int csd, int csc){
   if (sonuocdi == sodong*socot)
      output(dd);

   int list[8][3], spt;
   create(csd, csc, list, spt);

   for (int i=0; i<spt; i++){
      sonuocdi++;
      dd [list[i][1]] [list[i][2]] = sonuocdi;
      doing(list[i][1], list[i][2]);
      dd [list[i][1]] [list[i][2]] = 0;
      sonuocdi--;
   }
}

void main(){
   clrscr();
   input();
   doing(csdong, cscot);
   printf("Khong tim thay duong di nao thoa man bai toan MA DI TUAN");
   getch();
}