优先级队列广搜——坦克大战

客官°小女子只卖身不卖艺 2022-08-21 05:45 156阅读 0赞

坦克大战  
时间限制：1000 ms | 内存限制：65535 KB  
难度：3  
描述  
Many of us had played the game “Battle city” in our childhood, and some  
people (like me) even often play it on computer now.  
What we are discussing is a simple edition of this game. Given a map that  
consists of empty spaces, rivers, steel walls and brick walls only. Your task  
is to get a bonus as soon as possible suppose that no enemies will disturb  
you (See the following picture).

Your tank can’t move through rivers or walls, but it can destroy brick walls  
by shooting. A brick wall will be turned into empty spaces when you hit it,  
however, if your shot hit a steel wall, there will be no damage to the wall.  
In each of your turns, you can choose to move to a  
neighboring (4 directions, not 8) empty space, or shoot in one of the four  
directions without a move. The shot will go ahead in that direction, until it  
go out of the map or hit a wall. If the shot hits a brick wall, the wall  
will disappear (i.e., in this turn). Well, given the description of a map,  
the positions of your tank and the target, how many turns will you take at  
least to arrive there?  
输入  
The input consists of several test cases. The first line of each test case  
contains two integers M and N (2 <= M, N <= 300). Each of the following M  
lines contains N uppercase letters, each of which is one  
of ‘Y’ (you), ‘T’ (target), ‘S’ (steel wall), ‘B’ (brick wall), ‘R’ (river)  
and ‘E’ (empty space). Both ‘Y’ and ‘T’ appear only once. A test case of  
M = N = 0 indicates the end of input, and should not be processed.  
输出  
For each test case, please output the turns you take at least in a separate  
line. If you can’t arrive at the target, output “-1” instead.  
样例输入  
3 4  
YBEB  
EERE  
SSTE  
0 0  
样例输出  
8

算法很简单，就是用优先级队列广搜，但是做的时候却有一个bug死活都出不来，万般无奈之下看了看别人的Java代码，感觉算法没什么不同啊，就一个点一个点的测（唉！调试程序的功底还是不足啊！）。后来，就把next变量不是只用一个了，而是每次搜索都新建一个，然后，居，然，可，以，了！！到现在我还没搞懂，反正是public的为什么不能重复用，本来是想和C++一样节省空间用的，却有了致命性的bug，Java和c++的使用区别还有待学习啊！  
此外，Java中优先级队列的使用除了可以让类本身继承comparable接口使其具有比较能力，还可以写一个comparator，作为一个参数传到队列中去，然而总是wa，我也不知道到底哪儿错了！

public static Comparator<Point> myCmp = new Comparator<Point>() {
            //降序排列，小的应该在前面
            public int compare(Point o1, Point o2) {
                // TODO Auto-generated method stub
                return o2.step - o1.step;
            }
    
        };

note：

1. 要逐步积攒如何调试程序的经验和平时训练中的bug的积累
     2. 需要对Java中的对象进行更深层次的了解，一些“鸡毛蒜皮”的东西没必要省。

AC代码：

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.Scanner;
    
    
    class Point implements Comparable<Point>{
        public int x=0,y=0,step=0;
    
        @Override
        public int compareTo(Point o) {
            // TODO Auto-generated method stub
            return this.step - o.step;
        }
    
    }
    
    public class Main { 
    
        public static final boolean DEBUG = true;
        public static int M,N;
        public static char[][] map = new char[310][310];
        public static boolean[][] visited = new boolean[310][310];
        public final static int[] dirx = {-1,1,0,0};
        public final static int[] diry = {
       0,0,-1,1};
        public static Point S = new Point();
        public static PriorityQueue<Point> pque = new PriorityQueue<Point>();
    
        public static boolean isAvailabe(int nx,int ny){
            if((nx>=0&&nx<M&&ny>=0&&ny<N)&&(map[nx][ny]!='R'&&map[nx][ny]!='S')&&(!visited[nx][ny]))
                return true;
            return false;
        }
        public static int BFS() {
            //show();
            Point cur = new Point();
            int nx=0,ny=0;
            while(!pque.isEmpty()){
                cur = pque.remove();
                if(map[cur.x][cur.y]=='T') return cur.step;
                for(int i=0;i<4;i++){
       //
                    nx = cur.x + dirx[i];
                    ny = cur.y + diry[i];
                    if(isAvailabe(nx, ny)){
                        Point next = new Point();//是每次定义一个新的
                        if(map[nx][ny]=='E'||map[nx][ny]=='T'){
                            next.x = nx;
                            next.y = ny;
                            next.step = cur.step+1;
                            visited[nx][ny] = true; 
                            pque.offer(next);
                        }
                        else if(map[nx][ny]=='B'){
                            next.x = nx;
                            next.y = ny;
                            next.step = cur.step+2;//shot and turn
                            visited[nx][ny] = true; 
                            pque.offer(next);
                        }
                    }
                }
            }
            return -1;
        }
    
        public static void show(){
            System.out.println("Output map:");
            for(int i=0;i<M;i++){
                for(int j=0;j<N;j++) System.out.print(map[i][j]);
                System.out.println();
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(true){
                M = in.nextInt();
                N = in.nextInt();
                if(N==0&&M==0) break;
                String line = new String();
                for(int i=0;i<M;i++){
                    line = in.next();
                    map[i] = line.toCharArray();
                }
                for(int i=0;i<M;i++){
                    boolean flag = false;
                    for(int j=0;j<N;j++){
                        if(map[i][j]=='Y'){
                            S.x = i;
                            S.y = j;
                            S.step = 0;
                            flag = true;
                            break;
                        }
                    }
                    if(flag) break;
                }
                pque.clear();
                for(int i=0;i<M;i++){
                    Arrays.fill(visited[i], false);
                }
                visited[S.x][S.y] = true;
                pque.offer(S);
                int res = BFS();
                System.out.println(res);
            }
        }
    
    }