蒜头君回家 bfs

分析： 两种情况， 起点----钥匙-----家
起点-----家--------钥匙-----------家
如果分开考虑的话，无疑会复杂一点，
换种方向考虑。家是一个定点，起点是一个定点，钥匙是个转折点且钥匙有多个。这里 将钥匙的所在地定义为一个ys[][]二维数组，依次遍历每个钥匙，求出钥匙到家到起点的两个值，将二者相加即可，求出最小的即为 最短距离

代码如下：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Node{
int x;
int y;
int d;
public Node(int a,int b,int c){
this.x=a;
this.y=b;
this.d=c;
}
public Node(){}
}
public class Main {
public static char maze[][]=new char[2010][2010];
public static int n=0,m=0,x1=0,y1=0;
public static int [][]ys=new int[5000][2];
public static int count=0;
public static boolean in(int x,int y){
return x>=0 && x<n && y>=0 && y<m;
}
public static int dir[][]={{0,-1},{0,1},{1,0},{-1,0}};
public static int c1=-1,d1=-1;//c是第一个距离,d是第二个距离
public static void bfs(int x,int y){
Node no = new Node(x,y,0);
Queue q= new LinkedList();
q.offer(no);
boolean vis[][]=new boolean[2010][2010];
vis[x][y]=true;
c1=-1;d1=-1;
while(!q.isEmpty()){
Node n = q.poll();
if(maze[n.x][n.y]‘S’){
c1=n.d;
if(d1!=-1){
return;
}
}
if(maze[n.x][n.y]‘T’){
d1=n.d;
if(c1!=-1){
return;
}
}
for(int i=0;i<4;i++){
int tx=n.x+dir[i][0];
int ty=n.y+dir[i][1];
if(in(tx,ty) && !vis[tx][ty] && maze[tx][ty]!=’#’){
vis[tx][ty]=true;
q.offer(new Node(tx,ty,n.d+1));
}
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();m=sc.nextInt();
sc.nextLine();
for(int i=0;i<n;i++){
String s=sc.nextLine();
for(int j=0;j<m;j++){
maze[i][j]=s.charAt(j);
if(maze[i][j]==‘P’){
ys[count][0]=i;
ys[count++][1]=j;

    		}
    	}
    }
    int sum=10000;
    for(int i=0;i<count;i++){
    	bfs(ys[i][0],ys[i][1]);
    	int s=c1+d1;
    	if(s!=-2&&s<sum){
    		sum=s;
    	}
    }
    System.out.println(sum);

    
}

}