ABC088 D

問題

解析解答

• 入力操作

class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int H = scan.nextInt();
        int W = scan.nextInt();
        char[][] map = new char[H][W];
        int count = 0;
        for(int i = 0;i < H;i++){
            String a = scan.next();
            for(int j = 0;j < W;j++){
                map[i][j] = a.charAt(j);
                if(map[i][j] == '.'){
　　　　　　　　　　　// 白ますを数える
                    count++;
                }
            }
        }

• 基本設定

       int INF = Integer.MAX_VALUE;
        int sx = 0;  // start の座標
        int sy = 0;
        int gx = W-1;   // ゴールのインデックス
        int gy = H-1;
        int[][] d= new int[H][W];       //dp
        int[] dx = {1,0,-1,0};  // dx,dyの添字を揃えることで上下左右を選択できる
        int[]dy = {0,1,0,-1};
        Pair pair ;
        LinkedList<Pair> queue = new LinkedList<Pair>();
        for(int i = 0;i < H;i++){
            for(int j = 0;j < W;j++){
                d[i][j] = INF;                  //通過していないかの判定
            }
        }
        pair = new Pair(sy, sx);  // 初期値(0,0)
        queue.add(pair);
        d[sy][sx] = 0;

• 操作開始

　　　  while(!queue.isEmpty()){
            Pair x = new Pair();
            x = queue.removeFirst();  // Listの最初を削除して取得する
            if(x.from == gy && x.end == gx){  // ゴールに到達したら終了
                break;
            }
            for(int i = 0;i < 4;i++){
                int nx = x.end + dx[i];  // 移動先のx,y座標
                int ny = x.from + dy[i];
                if(0 <= nx && nx < W && 0 <= ny && ny < H && map[ny][nx] != '#' && d[ny][nx] == INF){
/*
0 <= nx && nx < W && 0 <= ny && ny < H   範囲内か判断
map[ny][nx] != '#'　　対象ますが黒マスでない
d[ny][nx] == INF       到達していない
*/
                    Pair go = new Pair(ny,nx);    
                    queue.add(go);
                    d[ny][nx] = d[x.from][x.end]+1;
                }
            }
 
        }
        if(d[gy][gx] == INF){
            System.out.println(-1);
            return;
        }
        System.out.println(count-d[gy][gx]-1);
    }
}

• Listに入れるPairクラス

class Pair implements Comparable{
    int from;   // y座標を表す
    int end;   // x 座標を表す
    public Pair(int s,int g) {
        this.from = s;
        this.end = g;
    }
    public Pair() {
    }
    public int compareTo(Object other) {
        Pair otherpair = (Pair)other;
        return end - otherpair.end;
    }
}

ACできました

• myanser