ここ最近、チーター本が詰まってからAOJに訪れて再帰の練習問題を探したりしていたのですが、幅優先探索の問題を見つけたので試しにコーディングしてみました。ですが、無限ループに入ってしまい(何回目だ・・・)うまくいきません。よろしければ、どこがおかしいかご指摘頂ければ嬉しいです。
問題:AOJ0202(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202)
コード:
import java.util.*;
public class Main {
int limit;
int[] dish;
int ans = Integer.MIN_VALUE;
boolean isPrime(int num) {
if(num < 2) return(false);
for(int r = 2; r * r <= num; r++) {
if(num % r == 0) return(false);
}
return(true);
}
int solve() {
Queue<Integer> sum = new LinkedList<Integer>();
sum.add(0);
int ans = 0;
while(!sum.isEmpty()) {
int now = sum.poll();
for(int r = 0; r < dish.length; r++) {
int next = now + dish[r];
if(next < limit) {
if(isPrime(next)) ans = Math.max(ans, next);
sum.add(next);
}
System.out.println(ans);
}
}
return(ans);
}
void doIt() {
Scanner stdIn =new Scanner(System.in);
while(true) {
int kind = stdIn.nextInt();
limit = stdIn.nextInt();
if(kind + limit == 0) break;
dish = new int[kind];
for(int r = 0; r < kind; r++) {
dish[r] = stdIn.nextInt();
}
System.out.println(solve());
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new Main().doIt();
}
}
この再帰とか、幅優先とかのアルゴリズムが、自分の中でしっかりしてくれないと次に進めない・・・(泣)