1.
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 291 - The House Of Santa Claus
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=4&problem=227&mosmsg=Submission+received+with+ID+8353319
*
* @author Manuel Hager
* @version 1.0, 10/27/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.088
*/
public class Main
{
private static class Point
{
public final String value;
public Point[] neigbors = null;
public Point(String str) {
this.value = str;
}
public void setNeigbors(Point... neigbors) {
this.neigbors = neigbors;
}
@Override public String toString() {
return value;
}
}
private static class Graph
{
private Map<Point, Map<Point, Boolean>> map;
public Graph() {
map = new HashMap<Point, Map<Point, Boolean>>();
}
public void add(Point a, Point b) {
if(map.containsKey(a)) {
Map<Point, Boolean> inside = map.get(a);
if(!inside.containsKey(b)) {
inside.put(b, new Boolean(false));
return;
}
}
else if(map.containsKey(b)){
Map<Point, Boolean> inside = map.get(b);
if(!inside.containsKey(a)) {
inside.put(a, new Boolean(false));
return;
}
}
Map<Point, Boolean> map2 = new HashMap<Point, Boolean>();
map2.put(b, new Boolean(false));
map.put(a, map2);
}
public boolean isUsed(Point a, Point b) {
if(map.containsKey(a)) {
Map<Point, Boolean> inside = map.get(a);
if(inside.containsKey(b))
return inside.get(b);
return isUsed(b, a);
}
else if(map.containsKey(b)) {
Map<Point, Boolean> inside = map.get(b);
if(inside.containsKey(a))
return inside.get(a);
return isUsed(b, a);
}
throw new RuntimeException("Should not happen!");
}
public boolean setUsed(Point a, Point b, boolean value) {
if(map.containsKey(a)) {
Map<Point, Boolean> inside = map.get(a);
if(inside.containsKey(b)) {
return inside.put(b, value);
}
else {
return setUsed(b, a, value);
}
}
else if(map.containsKey(b)) {
Map<Point, Boolean> inside = map.get(b);
if(inside.containsKey(a)) {
return inside.put(a, value);
}
else {
return setUsed(b, a, value);
}
}
throw new RuntimeException("Should not happen!");
}
public boolean isFinished() {
for(Map<Point, Boolean> currMap : map.values()) {
for(Boolean b : currMap.values()) {
if(!b)
return false;
}
}
return true;
}
}
public static void main(String[] args) throws IOException
{
Point p1 = new Point("1");
Point p2 = new Point("2");
Point p3 = new Point("3");
Point p4 = new Point("4");
Point p5 = new Point("5");
p1.setNeigbors(p2, p3, p5);
p2.setNeigbors(p1, p3, p5);
p3.setNeigbors(p1, p2, p4, p5);
p4.setNeigbors(p3, p5);
p5.setNeigbors(p1, p2, p3, p4);
Graph graph = new Graph();
graph.add(p1, p2);
graph.add(p1, p3);
graph.add(p1, p5);
graph.add(p2, p3);
graph.add(p2, p5);
graph.add(p3, p4);
graph.add(p3, p5);
graph.add(p4, p5);
startAt(p1, graph, new ArrayList<Point>());
}
private static boolean startAt(Point start, Graph graph, List<Point> list) {
list.add(start);
for(Point currNeigbor : start.neigbors)
{
if(!graph.isUsed(start, currNeigbor))
{
graph.setUsed(start, currNeigbor, true);
if(startAt(currNeigbor, graph, list))
{
System.out.println(listToString(list));
graph.setUsed(start, currNeigbor, false);
}
else
{
int index = list.lastIndexOf(currNeigbor);
while(list.size() -1 >= index) {
list.remove(index);
}
graph.setUsed(start, currNeigbor, false);
}
}
}
return graph.isFinished() ;
}
private static String listToString(List<Point> list) {
StringBuilder str = new StringBuilder(list.size());
for(Point p : list) {
str.append(p.toString());
}
return str.toString();
}
}
2. Erste Version: JAVA, [2] + Evgeni Pavlidis
/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/
import java.io.*;
public class Main {
private static final String FileOutputName = "nikolaus.out";
private int a[][] = { new int[] { 0, 1, 1, 0, 1 },
new int[] { 1, 0, 1, 0, 1 }, new int[] { 1, 1, 0, 1, 1 },
new int[] { 0, 0, 1, 0, 1 }, new int[] { 1, 1, 1, 1, 0 } };
private int b[] = new int[9];
private int sol = 0;
private PrintStream out;
Main(PrintStream out) {
this.out = out;
}
void run() {
back(1);
}
private void writeSol() {
for (int i = 0; i < 9; i++) {
out.print(b[i] + 1);
}
out.println();
}
void back(int k) {
int i;
if (9 == k)
writeSol();
else
for (i = 0; i < 5; i++)
if (a[i][b[k - 1]] == 1 && i != b[k - 1]) {
b[k] = i;
a[i][b[k - 1]] = 0;
a[b[k - 1]][i] = 0;
back(k + 1);
a[i][b[k - 1]] = 1;
a[b[k - 1]][i] = 1;
}
}
public static void main(String[] args) throws IOException {
PrintStream out = new PrintStream(System.out);
try {
new Main(out).run();
} finally {
out.close();
}
}
}
3.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 291 House of Santa Claus
*
* @author Reichart Robert
*
* Status : Accepted
* Runtime: 0.100
*/
import java.util.*;
class Main{
public static void main(String... args){
int[] number = {123153452,
123453152,
125431532,
132543512,
135234512,
134521532,
152134532,
153213452,
154312532,
123154352,
125135432,
125435132,
135123452,
135432152,
134523512,
152354312,
153254312,
154321352,
123513452,
125134532,
132153452,
135125432,
135432512,
134532152,
152345312,
153452132,
154325312,
123543152,
125315432,
132154352,
135215432,
134512352,
134532512,
153123452,
153452312,
154352132,
123451352,
125345132,
132534512,
134512532,
152135432,
153125432,
154312352,
154352312};
Arrays.sort(number);
for (int i=0;i<number.length;i++){
System.out.println(number[i]);
}
}
}