概要
解法
Sから1、1から2、2から3…の最短距離をそれぞれ求めて和を取る。 最短距離の計算は幅優先探索でOK
コード
import java.io.IOException; import java.util.*; class Main { public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); int H, W, N; H = in.nextInt(); W = in.nextInt(); N = in.nextInt(); String[] map = new String[H+3]; String str = ""; for(int i=0;i<W+2;i++) { str += "X"; } map[0] = str; in.nextLine(); for(int i=0;i<H;i++) { String s = in.nextLine(); map[i+1] = "X" + s + "X"; } map[H+1] = str; solve(map, H, W, N); } public static void solve(String[] ma, int H, int W, int N) { int ans = 0; int posx[] = new int[N+1]; int posy[] = new int[N+1]; // まずSの場所を探す for(int i=1;i<=H;i++) { int pos = ma[i].indexOf("S"); if(pos >= 0) { posx[0] = i; posy[0] = pos; ma[i].replace("S", "0"); break; } } for(int i=1;i<=H;i++) { for(int j=1;j<=N;j++) { int pos = ma[i].indexOf(""+j); if(pos >= 0) { posx[j] = i; posy[j] = pos; } } } for(int i=1;i<=N;i++) { ans += bfs(ma, posx[i-1], posy[i-1], H, W, ""+i); } System.out.println(ans); } public static int bfs(String[]ma, int sh, int sw, int H, int W, String target) { // 幅優先探索でtargetという文字列までの最短距離を計算 boolean[][] visited = new boolean[H+2][W+2]; Queue<P> q = new PriorityQueue<>(); q.offer(new P(sh, sw, 0)); // スタート地点を入れる while(!q.isEmpty()) { P p = q.poll(); visited[p.sh][p.sw] = true; // 数字が見つかった if((""+ma[p.sh].charAt(p.sw)).equals(target)) { return p.dist; } int dh[] = {0, 0, +1, -1}; int dw[] = {1,-1, 0, 0}; for(int i=0;i<4;i++) { int h = p.sh + dh[i]; int w = p.sw + dw[i]; if((""+ma[h].charAt(w)).equals("X") || visited[h][w]) continue; visited[h][w] = true; q.offer(new P(h, w, p.dist + 1)); } } assert (false); return -1; } } class P implements Comparable<P> { int sh; int sw; int dist; P(int sh, int sw, int dist) { this.sh = sh; this.sw = sw; this.dist = dist; } @Override public int compareTo(P p) { return this.dist - p.dist; } }