Untitled
unknown
plain_text
4 years ago
2.7 kB
6
Indexable
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> #define clr(ar) memset(ar, 0, sizeof(ar)) #define read() freopen("lol.txt", "r", stdin) #define valid(i, j) ((i) >= 0 && (i) < n && (j) >= 0 && (j) < n) struct Knight{ int i, j; int h, dis; }; bool flag, visited[52][52]; int dx[] = {-1, -1, 1, 1, -2, -2, 2, 2}; int dy[] = {-2, 2, -2, 2, -1, 1, -1, 1}; int n, m, ci, cj, path[52][52], hval[52][52]; int compare(const void* a, const void* b){ struct Knight x = (*(struct Knight*)a); struct Knight y = (*(struct Knight*)b); if (x.h == y.h) return (y.dis - x.dis); else return (x.h - y.h); } void increment(int i, int j){ int d, k, l; for (d = 0; d < 8; d++){ k = i + dx[d], l = j + dy[d]; if (valid(k, l)) hval[k][l]++; } } void decrement(int i, int j){ int d, k, l; for (d = 0; d < 8; d++){ k = i + dx[d], l = j + dy[d]; if (valid(k, l)) hval[k][l]--; } } void backtrack(int i, int j, int counter){ if (counter == m){ flag = true; for (i = 0; i < n; i++){ for (j = 0; j < n; j++){ printf("%5d", path[i][j]); } puts(""); } return; } struct Knight ar[8]; int d, k, l, len = 0; for (d = 0; d < 8; d++){ k = i + dx[d], l = j + dy[d]; if (valid(k, l) && !visited[k][l]){ ar[len].i = k, ar[len].j = l; ar[len].h = hval[k][l] - 1, ar[len].dis = ((k - ci) * (k - ci)) + ((l - cj) * (l - cj)); len++; } } qsort(ar, len, sizeof(struct Knight), compare); for (d = 0; d < len; d++){ k = ar[d].i, l = ar[d].j; decrement(k, l); path[k][l] = counter; visited[k][l] = true; backtrack(k, l, counter + 1); visited[k][l] = false; increment(k, l); if (flag) return; } } int main(){ int t, i, j, k, l, x, y; for (t = 0; ;t++){ scanf("%d %d %d", &n, &x, &y); if (feof(stdin)) break; if (t) puts(""); if ((n < 5) || (n & 1)) puts("No Circuit Tour."); else{ clr(hval); for (i = 0; i < n; i++){ for (j = 0; j < n; j++){ increment(i, j); } } x--, y--; m = (n * n) + 1; ci = (n >> 1), cj = (n >> 1); flag = false; clr(visited); path[x][y] = 1; visited[x][y] = true; backtrack(x, y, 2); } } return 0; }
Editor is loading...