Untitled

 avatar
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...