program MoebiusDames (input, output); { (c) 25/08/'97 Meinte Boersma Pascal-uitwerking van de NKP'97-opgave "Schaken op een Moebiusband" } const maxgrootte = 10; keer2 = 20; { = maxgrootte*2 } type band = array[0..keer2, 0..maxgrootte] of boolean; { true <--> vrij ;; (0,0) is linksboven } var {globaal} bord : band; n, m, run, R : integer; function vrij (var x, y : integer) : boolean; { zoekt eerste vrije plaats op bord vanaf positie (x, y) incl. naar rechtsonder en levert true <==> nog posities over en in (x, y) laatste vrije (of anders: geprobeerde (=(2n, m)) ) plaats } var hebbes : boolean; begin hebbes := false; while not hebbes and (y<m) do begin while not hebbes and (x<2*n) do begin hebbes := bord[x, y]; x := x+1; end; if not hebbes then begin x := 0; end; y := y+1; end; if hebbes then begin vrij := true; x := x-1; y := y-1; end else begin vrij := false; end; end; { vrij } procedure plaatsdame (x, y : integer); var i, j : integer; begin { horizontaal } for j := 0 to m-1 do begin bord[x, j] := false; end; { verticaal } for i := 0 to (2*n -1) do begin bord[i, y] := false; end; { kruis } for j := 0 to m-1 do begin bord[(x+m-j) mod m, j] := false; bord[(x+m+j) mod m, j] := false; end; end; { plaatsdame } function maxdames (dames, x, y : integer) : integer; var kopie : band; { kopie voor de backtracking } max, terug : integer; begin max := dames; kopie := bord; while vrij(x, y) do begin plaatsdame(x, y); terug := maxdames(dames+1, x, y); if terug > max then begin max := terug; end; bord := kopie; x := x+1; if x = 2*n then begin { over de rand } x := 0; y := y+1; end; end; maxdames := max; end; { maxdames } procedure instantie; var i, j : integer; begin for i := 0 to (2*n -1) do begin for j := 0 to m-1 do begin bord[i, j] := true; end; end; writeln(maxdames(0, 0, 0):1); end; { instantie } begin readln(R); for run := 1 to R do begin readln(n, m); instantie; end; end.