Poj Solution 3026

http://poj.org/problem?id=3026

import java.io.PrintWriter;  
 import java.util.LinkedList;  
 import java.util.Queue;  
 import java.util.Scanner;  
    
public class Main {  
  static class Point{  
  int x,y,step;  
   int result = 1;  
   char c;  
   public Point(int x, int y, char c){  
   this.x = x;  
    this.y = y;  
  this.c = c;  
    step = 1;  
  }  
  public Point(int x, int y,int step, char c){  
    this.x = x;  
   this.y = y;  
    this.c = c;  
    this.step = step;  
  }  
   @Override 
   public int hashCode() {  
    if(result != 1){  
     return result;  
    }  
    final int prime = 31;  
    result = 1;  
    result = prime * result + c;  
    result = prime * result + x;  
    result = prime * result + y;  
    return result;  
   }  
   @Override 
   public boolean equals(Object obj) {  
    if (this == obj)  
     return true;  
    Point other = (Point) obj;  
    if (c != other.c)  
     return false;  
    if (x != other.x)  
     return false;  
    if (y != other.y)  
     return false;  
    return true;  
   }  
      
  }  
  static int[][] all = new int[150][150];  
  static int[] DX = {0,-1,0,1};//e n w s  
  static int[] DY = {-1,0,1,0};  
  public static void main(String[] args) {  
   Scanner scn = new Scanner(System.in);  
  
   PrintWriter out = new PrintWriter(System.out);  

      
   int n = scn.nextInt(),x,y;  
   int num;//S �� A ����  
   char[][] data = new char[101][101];  
  int[][] table = new int[101][101];  
   Point[] points = new Point[101];  
   Point point;  
   String str;  
  while(n-- > 0){  
    x = scn.nextInt();  
    y = scn.nextInt();  
    
    scn.nextLine();  
    for(int i = 0; i < y; i++){  
     str = scn.nextLine();  
     data[i] = str.toCharArray();  
    }  
    //�õ�������������points������4  
   num = getNum(data,y,x,points);  
   for(int i = 0; i < num; i++){  
     bfs(data,table,points[i]);  
    }  
    out.println(prim(table, num));  
   }  
   out.flush();  
  }  
 private static void bfs(char[][] data, int[][] table, Point point) {  
   Queue<Point> queue = new LinkedList<Point>();  
   queue.add(point);  
   int x,y,nx,ny;  
   int px = all[point.x][point.y];  
   int[][] visted = new int[150][150];  
   while(!queue.isEmpty()){  
    point = queue.poll();  
    x = point.x;  
    y = point.y;  
    for(int i = 0; i < 4; i++){  
     nx = x + DX[i];  
    ny = y + DY[i];  
     if(data[nx][ny] == '#'){  
      continue;  
     }  
     if(visted[nx][ny] == 1){  
      continue;  
     }  
     visted[nx][ny] = 1;  
     if(data[nx][ny] == 'A' || data[nx][ny] == 'S'){  
      table[px][all[nx][ny]] = point.step;  
     }  
     queue.add(new Point(nx,ny,point.step + 1,data[nx][ny]));  
    }  
  }  
 }  

     
  /**  
   * �õ� y �� s ����  
   * @param data  
   * @param y  
   * @param x  
   * @return  
   */ 
  private static int getNum(char[][] data, int x, int y,Point[] points) {  
   int num = 0;  
   char c;  
   for(int i = 0; i < x; i++){  
    for(int j = 0; j < y; j++){  
     c = data[i][j];  
     if(c == 'A' || c == 'S'){  
      all[i][j] = num;  
      points[num] = new Point(i,j,c);  
      num++;  
     }  
    }  
   }  
   return num;  
  }  
  public static int prim(int[][] table, int n) {  
    
   int[] lowcost = new int[n];  
   boolean[] s = new boolean[n];  
   int sum = 0;  
   s[0] = true;// �ӵ�һ��λ�ÿ�ʼ  
   for (int i = 1; i < n; i++) {  
    lowcost[i] = table[0][i];  
    s[i] = false;  
   }  
   // �ҵ� j - s �е���СȨ��  
   for (int i = 1; i < n; i++) {  
    int min = Integer.MAX_VALUE;  
    int j = 1;  
   for (int k = 1; k < n; k++) {  
     if ((lowcost[k] < min) && (!s[k])) {  
      min = lowcost[k];  
      j = k;  
     }  
    }  
    s[j] = true;// ���뵽j ���뵽 s ������4  
    // sum += min;  
   for (int k = 1; k < n; k++) {  
     if (table[j][k] < lowcost[k] && (!s[k])) {  
      lowcost[k] = table[j][k];  
     }  
    }  
   }  
      
  for (int i = 0; i < n; i++) {  
    sum += lowcost[i];  
   }  
   return sum;  
  }  
    }