Я думаю, что самый простой способ решить это моделировать сетку в виде графика. Создайте ребро между двумя соседями, а также создайте одно ребро между двумя узлами одного типа. После этого простая BFS от источника до места назначения может ответить по кратчайшему пути между двумя узлами.
http://en.wikipedia.org/wiki/Breadth-first_search
Сложность O (V + E). V - количество узлов, 100x100, E - количество ребер
.
Люди здесь упоминают Дейкстру. Это решает, но это необходимо, так как все края стоят один. Дейкстра является частным случаем алгоритма A-star, поэтому A * также слишком много для этой проблемы.
Будьте проще, BFS!
Это O (R * C) время и O (R * C) пространственное решение:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class DanceBattle {
static final int INF = (int)(Integer.MAX_VALUE * 0.5);
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for(int i = 0; i < N ; ++i) {
int R = in.nextInt();
int C = in.nextInt();
int V = R*C;
int node = 0, start = 0, end = 0;
int nodeColor[] = new int[V];
List<Integer>[] colorMap = new List[10];
for(int color=0;color<10;++color)
colorMap[color] = new LinkedList<Integer>();
for(int r = 0; r < R; ++r) {
String row = in.next();
for(int c = 0; c<row.length(); ++c) {
char v = row.charAt(c);
if(v == 'S' ) start = node;
else if (v == 'E') end = node;
else if (v == 'W') nodeColor[node] = -1;
else {
int color = (int)(v - '0');
nodeColor[node] = color;
colorMap[color].add(node);
}
node++;
}
}
int neighborhood4[][] = new int[V][4];
for(int j =0 ; j< V; ++j) {
int c = j % C;
int r = (j - c)/C;
int grad = 0;
if(neighbors(r,c,r,c+1, R, C))
neighborhood4[j][grad++] = (r) * C + (c+1);
if(neighbors(r,c,r,c-1, R, C))
neighborhood4[j][grad++] = (r) * C + (c-1);
if(neighbors(r,c,r+1,c, R, C))
neighborhood4[j][grad++] = (r+1) * C + (c);
if(neighbors(r,c,r-1,c, R, C))
neighborhood4[j][grad++] = (r-1) * C + (c);
if(grad < 4)
neighborhood4[j][grad] = -1;
}
//bfs
int qbegin, qend;
int[] Q = new int[V];
int[] dist = new int[V];
for(int j=0; j<V; j++) dist[j] = INF;
dist[start] = 0;
qbegin = qend = 0;
Q[qend++] = start;
int complexity = 0;
while(qbegin != qend) {
int currNode = Q[qbegin++];
for(int j=0; j<4; j++) {
int neighbor = neighborhood4[currNode][j];
if(neighbor == -1) break;
int color = nodeColor[neighbor];
if(dist[neighbor] == INF && color != -1 ) {
Q[qend++] = neighbor;
dist[neighbor] = dist[currNode] + 1;
}
complexity++;
}
int color = nodeColor[currNode];
if (color == 0)
continue;
Iterator<Integer> iter = colorMap[color].iterator();
while(iter.hasNext()) {
int viz = iter.next();
if(dist[viz] == INF) {
Q[qend++] = viz;
dist[viz] = dist[currNode] + 1;
}
iter.remove();
complexity++;
}
}
System.out.printf("%d\n",dist[end]);
//System.out.printf("(compl. %d V=%d constant: %.2f)\n", complexity, V, ((float)complexity) / V);
}
}
private static boolean neighbors(int ar, int ac, int br, int bc, int R, int C) {
if(ar < 0 || ac < 0 || br < 0 || bc < 0) return false;
if(ar >= R || ac >= C || br >= R || bc >= C) return false;
return (Math.abs(ar - br) <= 1 && Math.abs(ac - bc) ==0) || (Math.abs(ar - br) == 0 && Math.abs(ac - bc) <=1);
}
}