Advertisement
Guest User

Untitled

a guest
Sep 24th, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.08 KB | None | 0 0
  1. import java.awt.Point;
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.     char[][] map;
  7.     int men,houses,n;
  8.     HashMap<Point,Integer> mapper;
  9.     int[][] g, cost;
  10.     int INF = 999999999;
  11.                        
  12.     int[] dx = new int[]{0,-1,0,1};
  13.     int[] dy = new int[]{-1,0,1,0};
  14.    
  15.     public void run()throws IOException{
  16.         BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  17.         int n,m;
  18.         String[] toks = bf.readLine().trim().split("[ ]+");
  19.         n = Integer.parseInt(toks[0]);
  20.         m = Integer.parseInt(toks[1]);
  21.        
  22.         while(n!=0 || m!=0){
  23.             map = new char[n][];
  24.             for(int i=0; i<map.length; i++) map[i] = bf.readLine().trim().toCharArray();
  25.             men=0;
  26.             houses=0;
  27.        
  28.             for(int i=0; i<n; i++){
  29.                 for(int j=0; j<m; j++){
  30.                     if(map[i][j]=='m') men++;
  31.                     else if(map[i][j]=='H') houses++;
  32.                 }
  33.             }
  34.            
  35.             mapper = new HashMap<Point, Integer>();
  36.             for(int i=0, mm=0, hh=men; i<map.length; i++){
  37.                 for(int j=0; j<map[0].length; j++){
  38.                     if(map[i][j]=='m') mapper.put(new Point(i,j), mm++);
  39.                     else if(map[i][j]=='H') mapper.put(new Point(i,j), hh++);
  40.                 }
  41.             }
  42.  
  43.             int sz = men+houses;
  44.             g = new int[sz+2][sz+2];
  45.             cost = new int[sz+2][sz+2];
  46.             for(int i=0; i<cost.length; i++){
  47.                 Arrays.fill(cost[i], INF);
  48.                 cost[i][i]=0;
  49.             }
  50.             for(int i=0; i<men; i++){
  51.                 g[sz][i]=1;
  52.                 cost[sz][i]=0;
  53.             }
  54.             for(int i=men+houses-1; i>=men; i--){
  55.                 g[i][sz+1]=1;
  56.                 cost[i][sz+1]=0;
  57.             }
  58.            
  59.             for(int i=0; i<map.length; i++){
  60.                 for(int j=0; j<map[0].length; j++){
  61.                     if(map[i][j]=='m') bfs(i,j);
  62.                 }
  63.             }
  64.                        
  65.             MinCostFlow mcf = new MinCostFlow(g, cost, sz, sz+1, INF);
  66.             mcf.run();
  67.             System.out.println(mcf.flowCost);
  68.            
  69.             toks = bf.readLine().trim().split("[ ]+");
  70.             n = Integer.parseInt(toks[0]);
  71.             m = Integer.parseInt(toks[1]);
  72.         }
  73.     }
  74.    
  75.     boolean isValid(int x, int y){
  76.         return x>=0 && x < map.length && y>=0 && y < map[0].length;
  77.     }
  78.    
  79.     void bfs(int x, int y){
  80.         int src = mapper.get(new Point(x,y));
  81.         Queue<QNode> q = new LinkedList<QNode>();
  82.         boolean[][] v = new boolean[map.length][map[0].length];
  83.         v[x][y]=true;
  84.         q.add(new QNode(x,y));
  85.         while(!q.isEmpty()){
  86.             QNode crnt = q.poll();
  87.             for(int i=0; i<4; i++){
  88.                 int xx = crnt.x + dx[i];
  89.                 int yy = crnt.y + dy[i];
  90.                 if(isValid(xx,yy) && !v[xx][yy]){
  91.                     v[xx][yy]=true;
  92.                     q.add(new QNode(xx,yy,crnt.steps+1));
  93.                     if(map[xx][yy]=='H'){
  94.                         int dest = mapper.get(new Point(xx,yy));
  95.                         g[src][dest]=1;
  96.                         cost[src][dest]=crnt.steps+1;
  97.                     }
  98.                 }
  99.             }
  100.         }
  101.     }
  102.    
  103.     public static void main(String[] args)throws IOException {
  104.         new Main().run();
  105.     }
  106.    
  107.     private class QNode{
  108.         int x,y,steps;
  109.        
  110.         public QNode(int xx, int yy){
  111.             x=xx;
  112.             y=yy;
  113.             steps=0;
  114.         }
  115.        
  116.         public QNode(int xx, int yy, int s){
  117.             x=xx;
  118.             y=yy;
  119.             steps=s;
  120.         }
  121.     }
  122. }
  123.  
  124. class MinCostFlow{
  125.     int[][] g, cost;
  126.     int n, src, sink, INF;
  127.     int flow, flowCost;
  128.     Point result;
  129.    
  130.     public MinCostFlow(int[][] g, int[][] cost, int src, int sink, int inf){
  131.         this.g=g;
  132.         this.cost = cost;
  133.         this.n=g.length;
  134.         this.src=src;
  135.         this.sink=sink;
  136.         this.INF = inf;
  137.         flow = flowCost = 0;
  138.     }
  139.    
  140.     Point augment(){
  141.         int[] parent = new int[n];
  142.         int[] dist = new int[n];
  143.         dist = new int[n];
  144.         Arrays.fill(dist, INF);
  145.         dist[src]=0;
  146.        
  147.         Arrays.fill(parent, -1);
  148.         parent[src]=src;
  149.  
  150.         boolean done=false;
  151.        
  152.         for(int itrs=0; !done && itrs<n; itrs++){
  153.             done=true;
  154.            
  155.             for(int i=0; i<n; i++){
  156.                 for(int j=0; j<n; j++){
  157.                     if(g[i][j]==0) continue;
  158.                     if(dist[j] > dist[i]+cost[i][j]){
  159.                         dist[j]=dist[i]+cost[i][j];
  160.                         parent[j]=i;
  161.                         done=false;
  162.                     }
  163.                 }
  164.             }
  165.            
  166.             if(done) break;
  167.         }
  168.  
  169.         if(parent[sink]==-1) return null;
  170.        
  171.         int minCap=INF;
  172.         int totalCost=0;
  173.         int tmp=sink;
  174.         while(parent[tmp]!=tmp){
  175.             totalCost+= cost[parent[tmp]][tmp];
  176.             if(g[parent[tmp]][tmp] < minCap) minCap = g[parent[tmp]][tmp];
  177.             tmp = parent[tmp];
  178.         }
  179.        
  180.         tmp=sink;
  181.         while(parent[tmp]!=tmp){
  182.             g[parent[tmp]][tmp] -= minCap;
  183.             g[tmp][parent[tmp]] += minCap;
  184.             tmp = parent[tmp];
  185.         }
  186.        
  187.         return result = new Point(minCap, totalCost);
  188.     }
  189.    
  190.     Point run(){
  191.         Point p=null;
  192.         flow=flowCost=0;
  193.         while((p=augment())!=null){
  194.             flow+=p.x;
  195.             flowCost+=p.x*p.y;
  196.         }
  197.        
  198.         return new Point(flow, flowCost);
  199.     }
  200. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement