/* * knights on a chess board. */ #include #include #include int board [15][15]; int N, M; unsigned long int count; int placed; void go (int r, int c); void mark (int r, int c); void unmark (int r, int c); int steps [][2] = { {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; int main (void) { char s [100]; int i, j; while (gets (s) != NULL) { sscanf (s, "%d %d", &M, &N); for (i = 0; i < 15; i++) for (j = 0; j < 15; j++) board [i][j] = 0; placed = 0; count = 0; go (2, 2); printf ("%lu\n", count); } return 0; } void go (int r, int c) { if (placed == N) { count++; return; } if (r > (M + 1)) { go (2, c + 1); return; } if (c > (M + 1)) return; go (r + 1, c); if (!board [r][c]) { mark (r, c); placed++; go (r + 1, c); placed--; unmark (r, c); } } void mark (int r, int c) { int i; for (i = 0; i < 8; i++) { board [r + steps [i][0]][c + steps [i][1]]++; } } void unmark (int r, int c) { int i; for (i = 0; i < 8; i++) { board [r + steps [i][0]][c + steps [i][1]]--; } }