Robot

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

#define N 5
#define MAX (N*N)
#define MUUR 1000
#define LEEG 1001
#define PAD 1002
#define MAXAFSTAND (1 << 30)

typedef struct {
  int x;
  int y;
  int waarde;
} Vakje;

void print(int a[N][N]) {
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      switch (a[i][j]) {
      case MUUR:
        printf("  # ");
        break;
      case LEEG:
        printf("    ");
        break;
      case PAD:
        printf("  + ");
        break;
      default:
        printf(" %2d ", a[i][j]);
      }
    }
    printf("\n");
  }
}

int totaleAfstand(Vakje pad[MAX], int n) {
  int afstand = 0;
  for (int i = 0; i < n; ++i) {
    afstand += pad[i].waarde;
  }
  return afstand;
}

void printPad(Vakje pad[MAX], int n) {
  int a[N][N];
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      a[i][j] = LEEG;
    }
  }
  for (int i = 0; i < n; ++i) {
    Vakje p = pad[i];
    if (p.x < N && p.x >= 0 && p.y < N && p.x >= 0) {
      a[pad[i].x][pad[i].y] = PAD;
    }
  }
  printf("lengte: %d\n", n);
  printf("afstand: %d\n", totaleAfstand(pad, n));
  print(a);
}

int aantalUitbreidingen(Vakje pad[MAX], int* lengte) { return 4; }

void maakVolgendeUitbreiding(int a[N][N], Vakje pad[MAX], int* lengte,
                             int buur) {
  int n = *lengte;
  assert(n > 0);
  *lengte = n + 1;
  pad[n] = pad[n - 1];
  if (buur == 0) {
    pad[n].x -= 1;
  } else if (buur == 1) {
    pad[n].y -= 1;
  } else if (buur == 2) {
    pad[n].x += 1;
  } else if (buur == 3) {
    pad[n].y += 1;
  }
  pad[n].waarde = a[pad[n].x][pad[n].y];
}

int besteAfstand = MAXAFSTAND;
int besteLengte = 0;
Vakje bestePad[MAX];

void backtrack(Vakje pad[MAX], int* lengte) {
  assert(*lengte > 0);
  *lengte = *lengte - 1;
}

int test(int a[N][N], Vakje pad[MAX], int lengte) {
  if (lengte >= MAX) {
    return 0;
  }
  for (int i = 0; i < lengte; ++i) {
    Vakje p = pad[i];
    if (p.x < 0 || p.x >= N || p.y < 0 || p.y >= N || a[p.x][p.y] == MUUR) {
      return 0;
    }
  }
  if (totaleAfstand(pad, lengte) >= besteAfstand) {
    return 0;
  }
  return 1;
}

int isCompleet(Vakje pad[MAX], int lengte) {
  return pad[lengte - 1].x == N - 1 && pad[lengte - 1].y == N - 1;
}

void registreer(Vakje pad[MAX], int lengte) {
  assert(totaleAfstand(pad, lengte) < besteAfstand);
  besteAfstand = totaleAfstand(pad, lengte);
  besteLengte = lengte;
  for (int i = 0; i < lengte; ++i) {
    bestePad[i] = pad[i];
  }
}

void zoek(int a[N][N], Vakje pad[MAX], int lengte) {
  if (!test(a, pad, lengte)) {
    return;
  }
  if (isCompleet(pad, lengte)) {
    printPad(pad, lengte);
    registreer(pad, lengte);
    return;
  }
  for (int i = 0; i < aantalUitbreidingen(pad, &lengte); ++i) {
    maakVolgendeUitbreiding(a, pad, &lengte, i);
    zoek(a, pad, lengte);
    backtrack(pad, &lengte);
  }
}

int main() {
  int a[N][N] = {
      {1, 1, 1, 1, 1},
      {5, MUUR, MUUR, MUUR, 1},
      {1, 2, 1, 1, 1},
      {1, 3, 10, MUUR, MUUR},
      {1, 15, 1, 1, 1},
  };

  print(a);

  Vakje pad[MAX];
  pad[0].x = 0;
  pad[0].y = 0;
  pad[0].waarde = a[0][0];
  int lengte = 1;

  zoek(a, pad, lengte);
  printPad(bestePad, besteLengte);
}