011
18.09.2002, 09:45 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Hallo Christian,
hier die im anderen Thread angesprochene Nicht-Rekursive Loesung. STL rules!
Habe auch 44 Moeglichkeiten gefunden.
| C++: |
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
// Die einzelnen Striche des Hauses seien wie folgt durchnummeriert:
// /\
// / \
// 0 / \ 1
// / 2 \
// +-------+
// |\ /|
// | \4 / |
// | \ / |
// 3 | X | 6
// | / \ |
// | /5 \ |
// |/ \|
// +-------+
// 7
typedef char zeichnung_t[9]; // Repraesentiert eine Zeichnung vom Haus
typedef std::map<std::string, bool> loesungen_t; // Map mit allen Zeichnungen, vlaue==1 -> Gueltig
//
// jeder Strich ist gerichtet, d.h an jedem Endounkt geht es mit 1..N anderen Strichen weiter.
// Diese Struktur dient dazu, diese Nachbarschaftsverältnisse zu beschreiben:
struct nachbarn_t
{
zeichnung_t nachbarn[2];
};
//
// Prüft, ob eine Zeichnung gültig ist, ob ohne absetzen gezeichnet werden kann
//
bool
ist_zeichnung_gueltig(
const zeichnung_t zeichnung)
{
//
// Dieses Array beschreibt alle möglichen Verbindungen. zB. ist Strich 1 an dem
// einen Ende mit Strich 0, am anderen mit den Strichen 2, 5, und 6 verbunden.
//
const nachbarn_t verbindungen[] = {
{ "234", "1" }, // 0
{ "0", "256" }, // 1
{ "034", "156" }, // 2
{ "024", "57"}, // 3
{ "023", "67"}, // 4
{ "37", "126"}, // 5
{ "125", "47"}, // 6
{ "35", "46" } // 7
};
//
// Prüfe alle striche
//
for(int i=1; i<8; ++i)
{
int richtung;
//
// Zunächst wird geprüft, ob die Striche zeichnung[ i ] und zeichnung[i-1] überhaupt
// verbunden sind. In richtung steht am ende 2, wenn keine Verbindung da ist, ansonsten
// entweder 0 oder 1
//
for(richtung=0; richtung<2; ++richtung)
{
if (std::strchr(verbindungen[zeichnung[ i ]-'0'].nachbarn[richtung], zeichnung[i-1]))
{
break;
}
}
if (2 == richtung) return false;
//
// Nun wird geprüft, ob es auch korrekt weiter geht. dh von Strich zeichnung[ i ] mit
// zeuichnung[i-1] über die Richtung 0 miteinander verbunden ist, dann muss zeichnung[ i ]
// über Richtung (1-richtung) mit zeichung[i+1] verbunden sein-
if (i<7)
{
richtung = 1-richtung;
if (!std::strchr(verbindungen[zeichnung[ i ]-'0'].nachbarn[richtung], zeichnung[i+1]))
return false;
}
}
return true;
}
int
main()
{
zeichnung_t zeichnung = "01234567";
loesungen_t loesungen;
zeichnung_t umgekehrt;
bool gueltig = false;
//
// Hauptschleife zur berechnung - Gehe alle Kombinationen durch,
// Wie das Haus gezeichnet werden koennte.
//
do
{
//
// Pruefe, ob umgekehrte Zeichnung schon getestet
// Wenn die Zeichnung auch umgekehrt noch nicht getestet wurde,
// wird der naechste if - Block durchlaufen
//
std::reverse_copy(zeichnung, zeichnung+8, umgekehrt);
umgekehrt[8] = 0;
gueltig = false;
if (loesungen.end() == loesungen.find(umgekehrt))
{
//
// Prüfe zeichnung auf Gueltigkeit
//
gueltig = ist_zeichnung_gueltig(zeichnung);
}
//
// Trage ergebnis in map ein
//
loesungen.insert(loesungen_t::value_type(zeichnung, gueltig));
}while (std::next_permutation(zeichnung, zeichnung+8));
//
// Ausgabe aller gueltigen Zeichnungen
//
for(loesungen_t::const_iterator i=loesungen.begin(); loesungen.end()!=i; ++i)
{
if (i->second) std::cout << i->first << std::endl;
}
}
|
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
Dieser Post wurde am 18.09.2002 um 09:46 Uhr von virtual editiert. |
.
.