//#=====================================================================================
//#
//#       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  ----------