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

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

[動作サンプル][1]

１行目：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
```

[1]: https://ideone.com/FcuFau

## コード

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

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

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

#### 動作確認

```java
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));
	}

}
```

# 再起処理を解除

```java

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 は解除できた。