C :: Aufgabe #75
1 Lösung
Das ist das Haus vom Nikolaus
Anfänger - C
von eulerscheZhl
- 12.03.2015 um 10:20 Uhr
Schreibe ein Programm, das alle Lösungen des Haus vom Nikolaus findet.
Lösungen:
Konsolenausgabe:
$ ./nikolaus
Weg #01 : 1-2-3-4-5-3-1-4-2
Weg #02 : 1-2-3-4-1-3-5-4-2
Weg #03 : 1-2-3-5-4-1-3-4-2
...
Weg #42 : 1-4-3-1-2-4-5-3-2
Weg #43 : 1-4-3-2-4-5-3-1-2
Weg #44 : 1-4-3-2-1-3-5-4-2
C-Code
/************************************
* nikolaus.c Haus vom Nikolaus
************************************/
#include <stdio.h>
#include <string.h>
/*
* 5
* +
* / \
* / \
* / \
* 4 +-----+ 3
* | |
* | |
* 1 +-----+ 2
*/
/* Struktur fuer Ecken und ihre Nachbarn */
typedef struct _corner {
int ends[4];
} corner_t;
corner_t corners[5] = {
{{2, 3, 4, 0}},
{{3, 4, 1, 0}},
{{4, 5, 1, 2}},
{{5, 1, 2, 3}},
{{3, 4, 0, 0}}};
/* Array fuer Kantenbelegung
* 0: Kante ist noch frei,
* 1: Kante wurde schon gezogen */
int edges[5][5];
/* rekursive Funktion zur Wegsuche im Graphen */
void traverse(int start) {
static int corner_stack[9];
static int corner_index = 0;
static int path_count = 0;
int c,i,j,k,end;
i = start-1;
corner_stack[corner_index] = start;
for (k=0; k<4; k++) {
end = corners[i].ends[k];
if (end > 0) {
j = end-1;
if (edges[i][j] == 0) {
edges[i][j] = edges[j][i] = 1;
corner_stack[++corner_index] = end;
if (corner_index == 8) {
path_count++;
printf("Weg #%02d : ", path_count);
for (c=0; c<=8; c++)
printf("%d%c", corner_stack[c], (c<8)?'-':'\n');
}
else {
traverse(end);
}
--corner_index;
edges[i][j] = edges[j][i] = 0;
}
}
}
}
/* main */
int main(void)
{
memset(edges, 0, 25*sizeof(int));
traverse(1);
return 0;
}