public final class saisyouzenikiki{
static int costLimit = 5+2+4+2+3+2+6+6+4;
static int LevelLimit = 20;
//スタックで使うデータ
class StackDataDef {
int cost = 0;
String Path ="";
StackDataDef(int cost,String Path){
this.cost = cost;
this.Path = Path;
}
};
//スタック
class StackClass {
int stackP;
StackDataDef stackData[];
StackClass(){
stackP = 0;
stackData = new StackDataDef[99999];
}
private void push(StackDataDef pushData){
stackData[stackP++] = pushData;
}
private StackDataDef pop(){
return stackData[--stackP];
}
boolean isEmpty(){ return stackP == 0; }
}
public static void main(String[] args) {
saisyouzenikiki mi = new saisyouzenikiki();
mi.main();
}
void main() {
StackClass st = new StackClass();
//Start With句
st.push(new StackDataDef(5,"AB"));
st.push(new StackDataDef(2,"AC"));
int LoopChk = 0;
while (st.isEmpty() == false){
StackDataDef priInfo = st.pop();
//枝切り条件
if (costLimit < priInfo.cost) continue;
else if (costLimit == priInfo.cost && LevelLimit <=priInfo.Path.length()) continue;
else if (20 < priInfo.Path.length()) continue;
else if (priInfo.Path.matches("^.*(..)\\1.*$")) continue; //無意味な再訪防止
//合格経路なら表示
boolean IsOK = true;
if (priInfo.Path.indexOf('A') == -1) IsOK = false;
else if (priInfo.Path.indexOf('B') == -1) IsOK = false;
else if (priInfo.Path.indexOf('C') == -1) IsOK = false;
else if (priInfo.Path.indexOf('D') == -1) IsOK = false;
else if (priInfo.Path.indexOf('E') == -1) IsOK = false;
else if (priInfo.Path.indexOf('F') == -1) IsOK = false;
if (IsOK){
System.out.println("経路は" + priInfo.Path + " コストは" + Integer.toString(priInfo.cost));
costLimit = priInfo.cost;
LevelLimit = priInfo.Path.length();
continue;
}
String Path;
int cost;
//connect by句
if (priInfo.Path.endsWith("A")){
Path = priInfo.Path + "B"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(AB|BA).*$")) cost +=5;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "C"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(AC|CA).*$")) cost +=2;
st.push(new StackDataDef(cost,Path));
}
else if (priInfo.Path.endsWith("B")){
Path = priInfo.Path + "A"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(BA|AB).*$")) cost +=5;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "C"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(BC|CB).*$")) cost +=4;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "D"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(BD|DB).*$")) cost +=2;
st.push(new StackDataDef(cost,Path));
}
else if (priInfo.Path.endsWith("C")){
Path = priInfo.Path + "A"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(CA|AC).*$")) cost +=2;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "B"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(CB|BC).*$")) cost +=4;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "D"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(CD|DC).*$")) cost +=3;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "E"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(CE|EC).*$")) cost +=2;
st.push(new StackDataDef(cost,Path));
}
else if (priInfo.Path.endsWith("D")){
Path = priInfo.Path + "B"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(DB|BD).*$")) cost +=2;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "C"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(DC|CD).*$")) cost +=3;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "E"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(DE|ED).*$")) cost +=6;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "F"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(DF|FD).*$")) cost +=6;
st.push(new StackDataDef(cost,Path));
}
else if (priInfo.Path.endsWith("E")){
Path = priInfo.Path + "C"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(EC|CE).*$")) cost +=2;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "D"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(ED|DE).*$")) cost +=6;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "F"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(EF|FE).*$")) cost +=4;
st.push(new StackDataDef(cost,Path));
}
else if (priInfo.Path.endsWith("F")){
Path = priInfo.Path + "D"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(FD|DF).*$")) cost +=6;
st.push(new StackDataDef(cost,Path));
Path = priInfo.Path + "E"; cost = priInfo.cost;
if (!priInfo.Path.matches("^.*(FE|EF).*$")) cost +=4;
st.push(new StackDataDef(cost,Path));
}
if (++LoopChk == 999999){
System.out.println("There is a Loop."); break;
}
}
}
}
