/*
  moebius.c -- C-uitwerking van de NKP'97-opgave
     "Schaken op een Moebiusband"
  (c) 31/08/'97 Meinte Boersma
*/

#include <stdio.h>

#define maxband 10

typedef int band[maxband*2][maxband];

band bord;
int n, m, run, R;


void kopieer (band src, band dest)
{
  int i, j;

  for (i=0; i<2*n; i++) {
    for (j=0; j<m; j++) {
      dest[i][j] = src[i][j];
    }
  }
}


int vrij (int *x, int *y)
{
  int hebbes = 0;

  while (!hebbes && (*y<m)) {
    while (!hebbes && (*x<2*n)) {
      hebbes = bord[*x][*y];
      (*x)++;
    }
    if (!hebbes) {
      *x = 0;
    }
    (*y)++;
  }
  if (hebbes) {
    (*x)--;
    (*y)--;
  }
  return(hebbes);
}


void plaatsdame (int x, int y)
{
  int i,j;

  /* horizontaal */
  for (j=0; j<m; j++) {
    bord[x][j] = 0;
  }
  /* verticaal */
  for (i=0; i<2*n; i++) {
    bord[i][y] = 0;
  }
  /* kruis */
  for (j=0; j<m; j++) {
    bord[(x+m-j)%m][j] = 0;
    bord[(x+m+j)%m][j] = 0;
  }
}


int maxdames (int dames, int x, int y)
{
  band kopie;
  int max, terug;

  max = dames;
  kopieer(bord, kopie);
  while (vrij(&x, &y)) {
    plaatsdame(x, y);
    terug = maxdames(dames+1, x, y);
    max = ((terug>max) ? terug : max);
    kopieer(kopie, bord);
    x++;
    if (x==2*n) {
      /* over de rand */
      x = 0;
      y++;
    }
  }
  return(max);
}


void instantie (void)
{
  int i, j;

  for (i=0; i<2*n; i++) {
    for (j=0; j<m; j++) {
      bord[i][j] = 1;
    }
  }
  printf("%d\n", maxdames(0,0,0));
}


int main (void)
{
  scanf("%d", &R);
  for (run=0; run<R; run++) {
    scanf("%d %d", &n, &m);
    instantie();
  }
  return(0);
}

Generated by Java2Html