Cod sursă (job #766481)

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_IMMORTALS 15
#define MAX_LINES 20
#define NONE -1

#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3
#define NUM_DIRS 4

typedef struct {
  int l, c;
} immortal;

typedef struct {
  int l, c, dir;
} move;

int d[NUM_DIRS][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

immortal imm[MAX_IMMORTALS];
move sol[MAX_IMMORTALS];
int a[MAX_LINES + 4][MAX_LINES + 4]; // matrice bordată cu două linii
int m, n, p;

void printSolution() {
  FILE *f = fopen("immortal.out", "w");
  for (int i = p; i > 1; i--) {
    fprintf(f, "%d %d %d %d\n",
            sol[i].l - 1,
            sol[i].c - 1,
            sol[i].l + 2 * d[sol[i].dir][0] - 1,
            sol[i].c + 2 * d[sol[i].dir][1] - 1);
  }
  fclose(f);
}

void debug(int k) {
  printf("Pe nivelul %d\n", k);
  for (int i = 0; i < m + 4; i++) {
    for (int j = 0; j < n + 4; j++) {
      printf("%3d", a[i][j]);
    }
    printf("\n");
  }
}

// Găsește o mutare când mai sunt k nemuritori rămași
void backtrack(int k) {
  if (k == 1) {
    printSolution();
    exit(0);
  }
  for (int i = 0; i < k; i++) {
    int l = imm[i].l, c = imm[i].c;
    for (int dir = 0; dir < NUM_DIRS; dir++) {
      int l1 = l + d[dir][0];
      int c1 = c + d[dir][1];
      int l2 = l1 + d[dir][0];
      int c2 = c1 + d[dir][1];
      if ((a[l1][c1] != NONE) && (a[l2][c2] == NONE)) {
        sol[k] = { l, c, dir };
        a[l][c] = NONE;
        imm[i] = { l2, c2 };
        a[l2][c2] = i;

        // Elimină nemuritorul mort (hehe) din vector
        int x = a[l1][c1]; // indicele mortului
        if (x < k - 1) {
          imm[x] = imm[k - 1];
          a[imm[x].l][imm[x].c] = x;
        }

        a[l1][c1] = NONE;

        backtrack(k - 1);

        // Acum pune totul la loc
        if (x < k - 1) {
          imm[k - 1] = imm[x];
          a[imm[k - 1].l][imm[k - 1].c] = k - 1;
          imm[x] = { l1, c1 };
        }

        a[l1][c1] = x;
        a[l2][c2] = NONE;
        imm[i] = { l, c };
        a[l][c] = i;
      }
    }
  }
}

int main(void) {
  FILE *f = fopen("immortal.in", "r");
  assert(fscanf(f, "%d %d %d", &m, &n, &p) == 3);

  // Bordează și inițializează matricea
  for (int i = 2; i <= m + 1; i++) {
    a[i][0] = a[i][1] = a[i][n + 2] = a[i][n + 3] = p;
  }
  for (int i = 2; i <= n + 1; i++) {
    a[0][i] = a[1][i] = a[m + 2][i] = a[m + 3][i] = p;
  }
  for (int i = 2; i < m + 2; i++) {
    for (int j = 2; j < n + 2; j++) {
      a[i][j] = NONE;
    }
  }

  // Bifează coordonatele unde există nemuritori
  for (int i = 0; i < p; i++) {
    int l, c;
    assert(fscanf(f, "%d %d", &l, &c) == 2);
    a[l + 1][c + 1] = 1;
  }
  fclose(f);

  // Colectează nemuritorii în ordinea liniilor
  int count = 0;
  for (int i = 2; i < m + 2; i++) {
    for (int j = 2; j < n + 2; j++) {
      if (a[i][j] != NONE) {
        a[i][j] = count;
        imm[count++] = {i, j};
      }
    }
  }
  assert(count == p);

  // debug(p);
  backtrack(p);
}