2012年10月6日

UVa 750 - 8 Queens Chess Problem


#include <stdio.h>

int times, R, C;

void run(int r, int *checkC, int *checkL, int *checkR, int *p) {
  if (r == 8) {
    printf("%2d     ", times++);
    int i, j;
    for (j = 0; j < 8; j++)
      printf(" %d", 8 - p[j]);
    puts("");
    return;
  }

  if (r == R) {
    p[R] = C;
    run(r + 1, checkC, checkL, checkR, p);
    return;
  }

  int c;
  for (c = 7; c >= 0; c--) {
    if (!checkC[c] && !checkL[r + c] && !checkR[r - c + 8]) {
      p[r] = c;
      checkC[c] = 1;
      checkL[r + c] = 1;
      checkR[r - c + 8] = 1;
      run(r + 1, checkC, checkL, checkR, p);
      checkC[c] = 0;
      checkL[r + c] = 0;
      checkR[r - c + 8] = 0;
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    times = 1;
    scanf("%d%d", &R, &C);
    puts("SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n");
    int checkC[8] = {}, checkL[16] = {}, checkR[16] = {}, p[8] = {};
    R--;
    C--;
    int tmp;
    tmp = R;
    R = C;
    C = tmp;
    C = 7 - C;
    checkC[C] = 1;
    checkL[R + C] = 1;
    checkR[R - C + 8] = 1;
    run(0, checkC, checkL, checkR, p);
    if (n) puts("");
  }
  return 0;
}

沒有留言:

張貼留言