開発メモ

開発用のメモです。

最短経路検索

多分もっと短くなる

import java.util.*;
import java.io.*;

public class Main {
    protected static String[][] matrix;
    protected static int min = 9999;
    public static void main (String[] args) throws Exception {
        // Java sun-jdk-1.7.
        try (
            InputStreamReader ir = new InputStreamReader(System.in);
            BufferedReader in = new BufferedReader(ir)) {
                String line = in.readLine();
                String[] xy = line.split(" ",-1);
                int x = Integer.parseInt(xy[0]);
                int y = Integer.parseInt(xy[1]);
                matrix = new String[y][x];
                int[] s = new int[]{0,0};
                int[] g = new int[]{0,0};
                int crow = 0;
                while ((line = in.readLine()) != null) {
                    String[] row = line.replace("1", "x").split(" ");
                    matrix[crow] = row;
                    int ccol = 0;
                    for (String cell : row) {
                        if ("s".equals(cell)) { s = new int[]{ crow, ccol }; }
                        if ("g".equals(cell)) { g = new int[]{ crow, ccol }; }
                        ccol++;
                    }
                    crow++;
                }
                add(s[1], s[0], 0);
            }
            System.out.println(min == 9999 ? "Fail" : min);
    }

    static final void add(int x, int y, int count) {
        try {
            if ("0".equals(matrix[y][x]) || "s".equals(matrix[y][x])) {
                if ("0".equals(matrix[y][x])) {
                    matrix[y][x] = String.valueOf(count);
                }
                if ("s".equals(matrix[y][x])) {
                    if (count != 0) {
                        return;
                    }
                }
                add(x+1,y+0,count+1);
                add(x+0,y+1,count+1);
                add(x-1,y-0,count+1);
                add(x-0,y-1,count+1);
            } else if ("g".equals(matrix[y][x])) {
                min = Math.min(count, min);
            } else {
                int old = Integer.parseInt(matrix[y][x]);
                if (old > count) {
                    matrix[y][x] = "0";
                    add(x,y,count);
                }
                return;
            }
        } catch (Exception e) {
            return;
        }
    }
}
Twitter: @asahina_alice