2195 Going Home

「2195 Going Home」の編集履歴（バックアップ）一覧はこちら

「2195 Going Home」(2006/05/14 (日) 00:27:57) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2195 Going Home
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int h, w;
         while(true){
             h = sc.nextInt();
             w = sc.nextInt();
             if(h==0&&w==0) break;
             
             char[][] floor = new char[h][w];
             for(int i=0;i<h;i++){
                 String s = sc.next();
                 for(int j=0;j<w;j++) floor[i][j] = s.charAt(j);
             }
             
             int m = 0;
             for(int i=0;i<h;i++){
                 for(int j=0;j<w;j++){
                     if(floor[i][j]=='H') m++;
                 }
             }
             
             int hx[] = new int[m];
             int hy[] = new int[m];
             int hc = 0;
             int mx[] = new int[m];
             int my[] = new int[m];
             int mc = 0;
             
             for(int i=0;i<h;i++){
                 for(int j=0;j<w;j++){
                     if(floor[i][j]=='H'){
                         hy[hc] = i;
                         hx[hc] = j;
                         hc++;
                     }
                     if(floor[i][j]=='m'){
                         my[mc] = i;
                         mx[mc] = j;
                         mc++;
                     }
                 }
             }
             
             int[][] dist = new int[m][m];
             for(int i=0;i<m;i++){
                 for(int j=0;j<m;j++){
                     dist[i][j] = Math.abs(hx[i]-mx[j]) + Math.abs(hy[i]-my[j]);
                 }
             }
             
             Solver sol = new Solver(m, dist);
             System.out.println(sol.solve());
         }
     }
 }
 
 class Solver {
     int n; //ノードの数
     int source; //ソース
     int sink; //シンク
     int[][] d; //距離行列
     int[][] c; //コスト行列
     int[][] a; //フローの上限
     int[][] f; //フロー
     int[] v; //始点からの距離
     int[] prev;
     int totalf; //トータルフロー
     int totalc; //トータルコスト
     public Solver(int m, int[][] dist) {
         n = 2*m+2;
         source = 2*m;
         sink = 2*m+1;
         d = new int[n][n];
         // init of d
         for(int i=0;i<n;i++) Arrays.fill(d[i], Integer.MAX_VALUE);
         for(int i=0;i<m;i++) d[source][i] = 0;
         for(int i=0;i<m;i++) d[m+i][sink] = 0;
         for(int i=0;i<m;i++){
             for(int j=0;j<m;j++){
                 d[i][m+j] = dist[i][j];
             }
         }
         
         c = new int[n][n];
         // init of c
         for(int i=0;i<n;i++){
             for(int j=0;j<n;j++) c[i][j] = d[i][j];
         }
         
         a = new int[n][n];
         // init of a
         for(int i=0;i<n;i++) Arrays.fill(a[i], 0);
         for(int i=0;i<m;i++) a[source][i] = 1;
         for(int i=0;i<m;i++) a[m+i][sink] = 1;
         for(int i=0;i<m;i++){
             for(int j=0;j<m;j++){
                 a[i][m+j] = 1;
             }
         }
         
         f = new int[n][n];
         for(int i=0;i<n;i++) Arrays.fill(f[i],0);
         v = new int[n];
         Arrays.fill(v, Integer.MAX_VALUE);
         prev = new int[n];
         Arrays.fill(prev, -1);
         totalf = 0;
         totalc = 0;
     }
     public int solve(){
         while(true){
             boolean flag;
             flag = dijekstra();
             if(!flag) break;
             tracePath();
             calcCost();
         }
         return totalc;
     }
     public void tracePath(){
         int u = sink;
         int v = prev[u];
         while(v!=-1){
             if(a[v][u]==1&&f[v][u]==0){
                 f[v][u] = 1;
                 totalc += d[v][u];
             }
             else if(a[u][v]==1&&f[u][v]==1){
                 f[u][v] = 0;
                 totalc -= d[u][v];
             }
             else throw new RuntimeException();
             
             u = v;
             v = prev[u];
         }
         totalf += 1;
     }
     public void calcCost(){
         for(int i=0;i<n;i++){
             for(int j=0;j<n;j++){
                 if(a[i][j]==1 && f[i][j]==0) c[i][j] = d[i][j] + v[i] - v[j];
                 else if(a[j][i]==1 && f[j][i]==1) c[i][j] = - d[j][i] + v[i] - v[j];
                 else c[i][j] = Integer.MAX_VALUE;
             }
         }
     }
     public boolean dijekstra(){
         boolean[] searched = new boolean[n];
         Arrays.fill(searched, false);
         Arrays.fill(v, Integer.MAX_VALUE);
         v[source] = 0;
         prev[source] = -1;
         
         int u = -1;
         int min = Integer.MAX_VALUE;
         while(true){
             min = Integer.MAX_VALUE;
             for(int i=0;i<n;i++){
                 if(!searched[i]&&v[i]<min){
                     u = i;
                     min = v[i];
                 }
             }
             
             if(min==Integer.MAX_VALUE) break;
             
             searched[u] = true;
             for(int i=0;i<n;i++){
                 if(searched[i]==false && c[u][i] < Integer.MAX_VALUE && v[i]>v[u]+c[u][i]){
                     v[i] = v[u]+c[u][i];
                     prev[i] = u;
                 }
             }
         }
         
         return searched[sink];
     }
 }