Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.awt.Point;
- import java.io.*;
- import java.util.*;
- public class Main {
- char[][] map;
- int men,houses,n;
- HashMap<Point,Integer> mapper;
- int[][] g, cost;
- int INF = 999999999;
- int[] dx = new int[]{0,-1,0,1};
- int[] dy = new int[]{-1,0,1,0};
- public void run()throws IOException{
- BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
- int n,m;
- String[] toks = bf.readLine().trim().split("[ ]+");
- n = Integer.parseInt(toks[0]);
- m = Integer.parseInt(toks[1]);
- while(n!=0 || m!=0){
- map = new char[n][];
- for(int i=0; i<map.length; i++) map[i] = bf.readLine().trim().toCharArray();
- men=0;
- houses=0;
- for(int i=0; i<n; i++){
- for(int j=0; j<m; j++){
- if(map[i][j]=='m') men++;
- else if(map[i][j]=='H') houses++;
- }
- }
- mapper = new HashMap<Point, Integer>();
- for(int i=0, mm=0, hh=men; i<map.length; i++){
- for(int j=0; j<map[0].length; j++){
- if(map[i][j]=='m') mapper.put(new Point(i,j), mm++);
- else if(map[i][j]=='H') mapper.put(new Point(i,j), hh++);
- }
- }
- int sz = men+houses;
- g = new int[sz+2][sz+2];
- cost = new int[sz+2][sz+2];
- for(int i=0; i<cost.length; i++){
- Arrays.fill(cost[i], INF);
- cost[i][i]=0;
- }
- for(int i=0; i<men; i++){
- g[sz][i]=1;
- cost[sz][i]=0;
- }
- for(int i=men+houses-1; i>=men; i--){
- g[i][sz+1]=1;
- cost[i][sz+1]=0;
- }
- for(int i=0; i<map.length; i++){
- for(int j=0; j<map[0].length; j++){
- if(map[i][j]=='m') bfs(i,j);
- }
- }
- MinCostFlow mcf = new MinCostFlow(g, cost, sz, sz+1, INF);
- mcf.run();
- System.out.println(mcf.flowCost);
- toks = bf.readLine().trim().split("[ ]+");
- n = Integer.parseInt(toks[0]);
- m = Integer.parseInt(toks[1]);
- }
- }
- boolean isValid(int x, int y){
- return x>=0 && x < map.length && y>=0 && y < map[0].length;
- }
- void bfs(int x, int y){
- int src = mapper.get(new Point(x,y));
- Queue<QNode> q = new LinkedList<QNode>();
- boolean[][] v = new boolean[map.length][map[0].length];
- v[x][y]=true;
- q.add(new QNode(x,y));
- while(!q.isEmpty()){
- QNode crnt = q.poll();
- for(int i=0; i<4; i++){
- int xx = crnt.x + dx[i];
- int yy = crnt.y + dy[i];
- if(isValid(xx,yy) && !v[xx][yy]){
- v[xx][yy]=true;
- q.add(new QNode(xx,yy,crnt.steps+1));
- if(map[xx][yy]=='H'){
- int dest = mapper.get(new Point(xx,yy));
- g[src][dest]=1;
- cost[src][dest]=crnt.steps+1;
- }
- }
- }
- }
- }
- public static void main(String[] args)throws IOException {
- new Main().run();
- }
- private class QNode{
- int x,y,steps;
- public QNode(int xx, int yy){
- x=xx;
- y=yy;
- steps=0;
- }
- public QNode(int xx, int yy, int s){
- x=xx;
- y=yy;
- steps=s;
- }
- }
- }
- class MinCostFlow{
- int[][] g, cost;
- int n, src, sink, INF;
- int flow, flowCost;
- Point result;
- public MinCostFlow(int[][] g, int[][] cost, int src, int sink, int inf){
- this.g=g;
- this.cost = cost;
- this.n=g.length;
- this.src=src;
- this.sink=sink;
- this.INF = inf;
- flow = flowCost = 0;
- }
- Point augment(){
- int[] parent = new int[n];
- int[] dist = new int[n];
- dist = new int[n];
- Arrays.fill(dist, INF);
- dist[src]=0;
- Arrays.fill(parent, -1);
- parent[src]=src;
- boolean done=false;
- for(int itrs=0; !done && itrs<n; itrs++){
- done=true;
- for(int i=0; i<n; i++){
- for(int j=0; j<n; j++){
- if(g[i][j]==0) continue;
- if(dist[j] > dist[i]+cost[i][j]){
- dist[j]=dist[i]+cost[i][j];
- parent[j]=i;
- done=false;
- }
- }
- }
- if(done) break;
- }
- if(parent[sink]==-1) return null;
- int minCap=INF;
- int totalCost=0;
- int tmp=sink;
- while(parent[tmp]!=tmp){
- totalCost+= cost[parent[tmp]][tmp];
- if(g[parent[tmp]][tmp] < minCap) minCap = g[parent[tmp]][tmp];
- tmp = parent[tmp];
- }
- tmp=sink;
- while(parent[tmp]!=tmp){
- g[parent[tmp]][tmp] -= minCap;
- g[tmp][parent[tmp]] += minCap;
- tmp = parent[tmp];
- }
- return result = new Point(minCap, totalCost);
- }
- Point run(){
- Point p=null;
- flow=flowCost=0;
- while((p=augment())!=null){
- flow+=p.x;
- flowCost+=p.x*p.y;
- }
- return new Point(flow, flowCost);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement