最短経路検索 Java / アルゴリズム

長すぎるきがする・・おおよそ１０分

動作サンプル

１行目：x y
２行目以下： 0 or 1 or s or g のスペース区切り

入力サンプル

1:4 5
2:0 s 0 1
3:0 0 1 0
4:0 1 1 0
5:0 0 1 g
6:0 0 0 0

コード

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;
        }
    }
}

実行クラスと計算クラスを分離

package jp.mirageworld.algorithm.route;

import java.util.Objects;

public class RouteCalc {

    public int calc(String[][] matrix) {
        int sy = 0;
        for (String[] row : matrix) {
            int sx = 0;
            for (String col : row) {
                if (Objects.equals(col, "s")) {
                    return calc(matrix, sy, sx, 0);
                }
                sx++;
            }
            sy++;
        }

        return -1;
    }

    public int calc(String[][] matrix, int sy, int sx, Integer count) {
        int min = 9999;
        try {
            if (Objects.equals("s", matrix[sy][sx]) && count > 0) {
                return min;
            }
            switch (matrix[sy][sx]) {
                case "0":
                    matrix[sy][sx] = count.toString();
                case "s":
                    break;
                case "g":
                    return count;
                default:
                    int x = Integer.parseInt(matrix[sy][sx]);
                    if (x > count) {
                        matrix[sy][sx] = "0";
                        return calc(matrix, sy, sx, count);
                    }
                    return min;
            }
            min = Math.min(min, calc(matrix, sy - 1, sx + 0, count + 1));
            min = Math.min(min, calc(matrix, sy + 0, sx - 1, count + 1));
            min = Math.min(min, calc(matrix, sy + 0, sx + 1, count + 1));
            min = Math.min(min, calc(matrix, sy + 1, sx + 0, count + 1));

        } catch (IndexOutOfBoundsException e) {
        }
        return min;
    }
}

動作確認

package jp.mirageworld.algorithm.route;

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import org.junit.Test;

public class RouteCalcTest {

    @Test
    public void testCalc() {
        String[][] m = {
                { "0", "s", "0", "1" },
                { "0", "0", "1", "0" },
                { "0", "1", "1", "0" },
                { "0", "0", "1", "g" },
                { "0", "0", "0", "0" },
        };

        RouteCalc rc = new RouteCalc();
        assertThat(rc.calc(m), is(9));
    }

}

再起処理を解除

package jp.mirageworld.algorithm.route;

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class RouteCalc {

    class Position {
        int y, x;

        public Position(int y, int x) {
            this.y = y;
            this.x = x;
        }

        @Override
        public int hashCode() {
            return y * 0xFF + x;
        }

        public void setValue(String value) {
            matrix[y][x] = value;
        }

        public String getValue() {
            return matrix[y][x];
        }

        public String getBlock() {
            try {
                return matrix[y][x];
            } catch (Exception e) {
                return "b";
            }
        }

        public Integer getInt() {
            return Integer.valueOf(matrix[y][x]);
        }

        public Position up() {
            return new Position(y + 1, x);
        }

        public Position down() {
            return new Position(y - 1, x);
        }

        public Position right() {
            return new Position(y, x + 1);
        }

        public Position left() {
            return new Position(y, x - 1);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Position) {
                return this.hashCode() == ((Position) obj).hashCode();

            }
            return false;
        }
    }

    int pos = 0;
    int min = Integer.MAX_VALUE;
    String[][] matrix;

    Set<Position> exec = new HashSet<>();
    Set<Position> next = new HashSet<>();

    public int calc(String[][] matrix) {

        this.matrix = matrix;

        int sx = -1;
        int sy = -1;

        for (int y = 0; y < matrix.length; y++) {
            for (int x = 0; x < matrix[y].length; x++) {
                if (Objects.equals(matrix[y][x], "1")) {
                    matrix[y][x] = "b";
                }
                if (Objects.equals(matrix[y][x], "s")) {
                    sx = x;
                    sy = y;
                }
            }
        }

        if (sx == -1 || sy == -1) {
            throw new IllegalArgumentException("start not found");
        }
        return calc(sy, sx);
    }

    public int calc(int y, int x) {
        next.add(new Position(y, x));
        do {
            exec = new HashSet<>(next);
            next.clear();
            exec.forEach(this::calc);
            pos++;
        } while (!next.isEmpty());
        return min;
    }

    public void calc(Position start) {
        if (pos > min) {
            return;
        }
        switch (start.getBlock()) {
        case "g":
            // ゴール
            min = Math.min(min, pos);
            return;

        case "s":
            if (pos != 0) {
                return;
            }
            // スタート
            break;

        case "0":
            int c = start.getInt();
            if (c != 0 && c < pos) {
                return;
            }
            if (c == 0 || c > pos) {
                start.setValue(Integer.toString(pos));
            }
            break;
        }

        next.add(start.up());
        next.add(start.down());
        next.add(start.right());
        next.add(start.left());

        next.removeIf(i -> Objects.equals("b", i.getBlock()));
        next.removeIf(i -> Objects.equals("s", i.getBlock()));

    }
}

とりあえず前コードだと問題になってた大規模迷路の stack overflow は解除できた。