AOJ 0558 Cheese

　前回のMysterious Wormの復習として、Cheese(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558)
という問題を解いてみました。これまた探索で良く出るグリッド系の問題なのですが・・・悔しい限りですがサンプル３が通らない。なぜか無限ループ。もう、自分が上手く行かなすぎて悲しくなってきます・・・(T_T)特に、同じ所でなんどもつまづく事が・・・

import java.util.*;
public class Main {
    String[] map; //探索域の地図
    class Rat {
        int cost;//時間
        int hp;//体力
        int target;//対象工場の残り数
        int x, y;//x座標y座標
        Rat(int cost, int hp, int target, int x, int y) {//コンストラクタ
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.hp = hp;
            this.target = target;
        }
    }

    private int solve(int x, int y, int n) {
        Queue<Rat> open = new LinkedList<Rat>();//ねずみの状態を格納しておくopen
        boolean[][] closed = new boolean[map.length][map[0].length()];//訪れた工場をメモしておくclosed

        //openに初期状態を入れる・・・秒数0、体力1、対象工場残り数n、x座標x、y座標y
        open.add(new Rat(0, 1, n, x, y));
        //東、西、南、北の順に進む
        int[] fdx = new int[]{1, -1, 0, 0};
        int[] fdy = new int[]{0, 0, -1, 1};
        //幅優先探索
        while(!open.isEmpty()) {
            //状態取得
            Rat temp = open.poll();  //あるネズミを取り出す
            int cost = temp.cost;    //秒数
            //System.out.println(cost);
            int hp = temp.hp;        //体力
            int target = temp.target;//対象工場の残り数
            int grid_x = temp.x;     //x座標
            int grid_y = temp.y;     //y座標
            temp = null;
            //もし、全ての工場のチーズを食べたならば秒数を返す
            if(target == 0) return(cost);
            //移動開始
            for(int r = 0; r < fdx.length; r++) {
                int nextcost = cost + 1;    //秒数が１進む
                int nexthp = hp;            //体力はまだ変化するか分からない
                int nexttarget = target;    //対象工場の残り数も同様
                int nextx = grid_x + fdx[r];//x座標を変化
                int nexty = grid_y + fdy[r];//y座標を変化
                //探索範囲外に出たり、障害物があったりしたらこのケースは無視
                if(nextx < 0 || nexty < 0 || nextx >= map[0].length() || nexty >= map.length || map[nexty].charAt(nextx) == 'X') continue;
                //工場のみ対象として行う処理
                if(map[nexty].charAt(nextx) != '.' && map[nexty].charAt(nextx) != 'S') {
                    if(hp >= (map[nexty].charAt(nextx) - '0') && !closed[nexty][nextx]) {
                        nexthp++;    //チーズを１つ食べたので体力が1増える
                        nexttarget--;//対象工場の残り数が減る
                        closed[nexty][nextx] = true;//訪れた事を記録
                    }
                    //System.out.println(map[nexty].charAt(nextx));
                }
                //進んだ状態を追加
                open.add(new Rat(nextcost, nexthp, nexttarget, nextx, nexty));
            }
            //System.out.println("for end");
        }
        return(-1);
    }

    void doIt() {
        Scanner stdIn = new Scanner(System.in);
        int height = stdIn.nextInt();
        int width = stdIn.nextInt();
        int n = stdIn.nextInt();
        map = new String[height];
        int x = -1, y = -1;
        for(int r = 0; r < height; r++) {
            map[r] = stdIn.next();
            for(int c = 0; c < width; c++) {
                if(map[r].charAt(c) == 'S') {
                    x = c; y = r;
                }
            }
        }
        int ans = solve(x, y, n);
        System.out.println(ans);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new Main().doIt();
    }
}

前回からかなり書き方が変わったと思うのですが・・・
何かおかしい点、気になる点がありましたら、教えて頂けると私の全てのつけめん侍が喜びます。