Das ist das Haus vom Nikolaus

C :: Aufgabe #75 :: Lösung #1

1 Lösung

#75

Anfänger - C von eulerscheZhl - 12.03.2015 um 10:20 Uhr

Schreibe ein Programm, das alle Lösungen des Haus vom Nikolaus findet.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von devnull (8870 Punkte) - 28.12.2015 um 20:34 Uhr

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;
}