#include <stdio.h>
#include <conio.h>

#define NX 50
#define NY 50
#define DAME -1

int damen(int anzahl, int feld[NX][NY], int dimX, int dimY);

void setzeDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY);

void loescheDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY);

void initFeld(int feld[NX][NY], int dimX, int dimY);

void ausgabeFeld(int feld[NX][NY], int dimX, int dimY);

int main()
{
	int feld[NX][NY];

   int anzahl, dimX, dimY;

   printf("Wie gross soll das Feld sein (x,y)?\n");
   scanf("%d %d", &dimX, &dimY);
   printf("Wie viele Damen?\n");
   scanf("%d", &anzahl);

   initFeld(feld,NX,NY);
   if (damen(anzahl,feld,dimX,dimY))
	   ausgabeFeld(feld,dimX,dimY);
   else
   	printf("Keine Lösung!\n");

   getch();
}

void initFeld(int feld[NX][NY], int dimX, int dimY)
{
	int x,y;
   for (x=0; x<dimX; ++x)
   	for(y=0; y<dimY; ++y)
      	feld[x][y] = 0;
}

void ausgabeFeld(int feld[NX][NY], int dimX, int dimY)
{
	int x,y;
   printf("\n Feld:\n");
   for (y=0; y<dimY; ++y){
   	for(x=0; x<dimX; ++x)
      	printf(" %3d",feld[x][y]);
      printf("\n");
      }
}


void setzeDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY)
{
	int x,y;

   for (x=0; x<dimX; ++x)
   	++feld[x][posY];

   for (y=0; y<dimY; ++y)
   	++feld[posX][y];


   if (posX >=posY) {
   	x = posX - posY;
   	y = 0;
      }
   else {
   	x = 0;
      y = posY-posX;
      }
   while(x<dimX && y<dimY) {
   	++feld[x][y];
      ++x;
      ++y;
      }

//   if (posX <=posY) {   // FALSCH !!!
   if (posX + posY <= dimX -1) {
   	y = posX + posY;
   	x = 0;
      }
   else {
   	y = dimY -1;
      x = posX - (y - posY);
      }
   while(x<dimX && y>=0) {
   	++feld[x][y];
      ++x;
      --y;
      }

   feld[posX][posY] = -1;
}

void loescheDame(int posX, int posY, int feld[NX][NY], int dimX, int dimY)
{
	int x,y;

   for (x=0; x<dimX; ++x)
   	--feld[x][posY];

   for (y=0; y<dimY; ++y)
   	--feld[posX][y];


   if (posX >=posY) {
   	x = posX - posY;
   	y = 0;
      }
   else {
   	x = 0;
      y = posY-posX;
      }
   while(x<dimX && y<dimY) {
   	--feld[x][y];
      ++x;
      ++y;
      }

//   if (posX <=posY) {
   if (posX + posY <= dimX -1) {
   	y = posX + posY;
   	x = 0;
      }
   else {
   	y = dimY -1;
      x = posX - (y - posY);
/*      if (x < 0||y<0) {
      	printf("Oh oh: posX:%d, posY:%d => x,y:%d,%d\n",posX,posY,x,y);
         getch(); exit(0);
      }*/
      }
   while(x<dimX && y>=0) {
   	--feld[x][y];
      ++x;
      --y;
      }

   feld[posX][posY] = 0;
}


int damen(int anzahl, int feld[NX][NY], int dimX, int dimY)
{
	int x,y,erg =0;

   if (anzahl == 0) erg =1;
   else
   	for (y=0; y<dimY && !erg; ++y)
      	for (x=0; x<dimX && !erg; ++x)
         	if (feld[x][y] == 0)
            {
            	setzeDame(x,y,feld,dimX,dimY);
               if (damen(anzahl-1,feld,dimX,dimY)==1)
               	erg = 1;
               else
               	loescheDame(x,y,feld,dimX,dimY);
            }
   return erg;
}
