長すぎるきがする・・おおよそ１０分
１行目：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 は解除できた。