幅優先探索の練習にと思い、AOJ0179 Mysterious Worm(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0179)
に挑戦しました。ですが、サンプルすらまともに合わないという悲惨な結果となってしまいました。ソースコードについて、何か悪い点、考え方が間違っている点などご指摘頂けたら幸いです!m(T^T)m
import java.util.*;
public class Main {
char node(char a, char b) {
char[] chr = {'r', 'g', 'b'};
for(int r = 0; r < chr.length; r++) {
if(chr[r] != a && chr[r] != b) return(chr[r]);
}
return('E'); //恐らく無いが、エラー回避のため
}
boolean ok(char[] wormc) {
for(int r = 0; r < wormc.length - 1; r++) {
if(wormc[r] != wormc[r + 1]) return(false);
}
return(true);
}
void doIt() {
Scanner stdIn = new Scanner(System.in);
while(stdIn.hasNext()) {
Queue<String> wormq = new LinkedList<String>();
Queue<Integer> time = new LinkedList<Integer>();
String worm = stdIn.next();
if(worm.length() == 1) break;
time.add(0);
wormq.add(worm);
while(!time.isEmpty()) {
int now = time.poll();
boolean flag = false;
for(int k = 0; k < wormq.size(); k++) {
String nowW = wormq.poll();
char[] wormc = nowW.toCharArray();
for(int r = 0; r < wormc.length - 1; r++) {
int next = now + 1;
if(ok(wormc)) {
flag = true;
if(time.isEmpty()) time.add(now);
break;
}
if(wormc[r] != wormc[r + 1]) {
char a = wormc[r], b = wormc[r + 1];
wormc[r] = wormc[r + 1] = node(a, b);
//System.out.println(new String(wormc));
}
time.add(next);
wormq.add(new String(wormc));
//System.out.println(next);
}
if(flag) break;
}
if(flag) break;
}
System.out.println(time.poll());
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new Main().doIt();
}
}