/*
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