题目描述

不知道这个题目为什么会有一些错觉，需要记录弹出的的次数，在队列中记录弹出的数字，是应用在连通块问题中的。

而题目要求是记录到达某一点的最小步数，所以需要采用一个单独的数组记录距离

代码

package bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class xyxy{
    int x;
    int y;
    public xyxy(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

}
public class 武士风度的牛 {

    public static int c,r,stx,sty,endx,endy,cnt;
    public static int N=160;

    public static int dist[][]=new int [N][N];

    public static String g[]=new String [N];
    public static int dx[]= {-1,-1,-2,-2,1,1,2,2};
    public static int dy[]= {-2,2,-1,1,-2,2,1,-1};

    public static int  bfs (int x,int y) {
        Queue<xyxy> queue = new LinkedList<xyxy>();
        queue.add(new xyxy(x, y));

        dist[x][y]=0;

        while(!queue.isEmpty()){
            xyxy xy=queue.poll();

            for(int i=0;i<8;i++){
                int a=xy.x+dx[i];
                int b=xy.y+dy[i];
                if(a<0 || a>=r || b<0 ||b>=c) continue;
                if(dist[a][b]!=-1) continue;
                if(g[a].charAt(b)=='*') continue;

                if(a==endx && b==endy) return dist[xy.x][xy.y]+1;

                queue.add(new xyxy(a, b));
                dist[a][b]=1+dist[xy.x][xy.y];



            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
     BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
     String p[]=bufferedReader.readLine().split(" ");
     c=Integer.parseInt(p[0]);
     r=Integer.parseInt(p[1]);
     for(int i=0;i<r;i++){
         g[i]=bufferedReader.readLine();
         for(int j=0;j<c;j++){
             if(g[i].charAt(j)=='H'){
                 endx=i;endy=j;
             }
             if(g[i].charAt(j)=='K'){
                 stx=i;sty=j;
             }

         }
     }

     for(int i=0;i<N;i++){
         Arrays.fill(dist[i], -1);
     }

    System.out.println(bfs(stx, sty));
    }

}