1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
//#=====================================================================================
//#
//# Filename: quadrat.cc
//#
//# Description: Suchaufgabe "Buchstabenquadrat"
//#
//# Version: 1.0
//# Created: 30.08.2002
//# Revision: none
//# Compiler: GNU C/C++
//#
//# Author: Dr.-Ing. Fritz Mehner (Mn)
//# Company: Fachhochschule Südwestfalen, Iserlohn
//# Email: mehner@fh-swf.de
//#
//#=====================================================================================
using namespace std;
// ##### HEADER FILE INCLUDES ######################################################
#include <iostream>
// ##### VARIABLES - LOCAL TO THIS SOURCE FILE ###################################
const int n = 4; // Dimension des Quadrats
char quadrat[n][n] = { // Buchstabenquadrat
{ 'S', 'R', 'G', 'D' },
{ 'O', 'F', 'A', 'E' },
{ 'N', 'U', 'B', 'L' },
{ 'T', 'S', 'P', 'E' } };
char buffer[1024]; // Puffer zum Aufbau der gefundenen Zeichenketten
int erreicht[1024]; // Stapel zur Speicherung der erreichten Positionen
int p; // Stapelzeiger
// ##### FUNCTION DEFINITIONS - LOCAL TO THIS SOURCE FILE ########################
//----------------------------------------------------------------------
// weiter
// Prüfen, ob ein Platz in der Matrix schon einmal erreicht wurde
//----------------------------------------------------------------------
bool
weiter ( int i, int j )
{
int k, pos = 10*i+j;
if( i<0 || i>=n || j<0 || j>=n )
return false; // Position außerhalb der Matrix
for ( k=0; k<p; k+=1 )
if(erreicht[k] == pos)
return false;
return true;
} // ---------- end of function weiter ----------
//----------------------------------------------------------------------
// suche
// Rekursiver Durchlauf durch die Matrix quadrat
//----------------------------------------------------------------------
void
suche ( int i, int j )
{
int di, dj;
int pos = 10*i+j; // Postition in der Matrix codieren
buffer[p] = quadrat[i][j]; // aktuelles zeichen in den Ausgabepuffer
erreicht[p] = pos; // erreichte Position in die Merkliste
p++; // Stapelzeiger erhöhen
buffer[p] = '\0'; // Zeichenkette im Ausgabepuffer abschließen
cout << buffer << "\n"; // Puffer ausgeben
for ( di=-1; di<=+1; di+=1 )
for ( dj=-1; dj<=+1; dj+=1 )
if ( weiter( i+di,j+dj) ) // Erreichbarkeit des Nachbarn prüfen
suche ( i+di,j+dj ); // Aufruf für die Nachbarn
p--; // Stapelzeiger vermindern
return ;
} // ---------- end of function suche ----------
//----------------------------------------------------------------------
// Hauptprogramm
//----------------------------------------------------------------------
int
main ( int argc, char *argv[] )
{
int i, j;
//----------------------------------------------------------------------
// Rekursion beginnt der Reihe nach bei jedem Matrixelement
//----------------------------------------------------------------------
for ( i=0; i<n; i+=1 )
for ( j=0; j<n; j+=1 )
{
p = 0;
suche(i,j);
}
return 0;
} // ---------- end of function main ----------
|
