网易牢笼问题 70%

网易大哥请告诉我哪里是出口?

import java.util.*;

public class MiGong {

    static class Step{
        public int dx;
        public int dy;

        public Step(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Step step = (Step) o;
            return dx == step.dx &&
                    dy == step.dy;
        }

        @Override
        public int hashCode() {

            return Objects.hash(dx, dy);
        }
    }

    private static int m, n, sx, sy, tx, ty;
    private static List<Step> step_list = new ArrayList<>();
    private static List<String> room = new ArrayList<>();
    private static Map<String, Integer> stepIntegerMap = new HashMap<>();

    private static void getMaxStepsSolution(){
        Queue<Step> stepQueue = new LinkedList<>();
        stepQueue.offer(new Step(sx, sy));
        stepIntegerMap.put(sx + " " + sy, 0);
        stepIntegerMap.put((m - 1) + " " + (n - 1), Integer.MAX_VALUE);
        int pos_x, pos_y;
        while (!stepQueue.isEmpty()){
            Step step = stepQueue.poll();
            //到达终点
            if(step.dx == m - 1 && step.dy == n - 1){
                continue;
            }else{
                for (Step step1
                        :
                        step_list){
                    pos_x = step.dx + step1.dx;
                    pos_y = step.dy + step1.dy;
                    if(pos_x < 0 || pos_x > m - 1 || pos_y < 0 || pos_y > n -1){
                        continue;
                    }
                    if( room.get(pos_x).charAt(pos_y) == '.'){

                        if(stepIntegerMap.containsKey(pos_x + " " + pos_y)){
                            if (stepIntegerMap.get(pos_x + " " + pos_y) > stepIntegerMap.get(step.dx + " " + step.dy) + 1){
                                stepIntegerMap.put(pos_x + " " + pos_y, stepIntegerMap.get(step.dx + " " + step.dy) + 1);
                                stepQueue.offer(new Step(pos_x, pos_y));
                            }
                        }else{
                            stepIntegerMap.put(pos_x + " " + pos_y, stepIntegerMap.get(step.dx + " " + step.dy
                            ) + 1);
                            stepQueue.offer(new Step(pos_x, pos_y));
                        }

                    }
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        for(int i = 0; i < m; i++){
            String string = scanner.next();
            room.add(string);
            int j = string.indexOf('.');
            if(j != -1){
                stepIntegerMap.put(i + " " + j, Integer.MAX_VALUE);
            }
        }
        sx = scanner.nextInt();
        sy = scanner.nextInt();
        int steps = scanner.nextInt();
        int i = 0;
        int dx, dy;
        while(i < steps){
            dx = scanner.nextInt();
            dy = scanner.nextInt();
            Step step = new Step(dx,dy);
            step_list.add(step);
            i++;
        }
        getMaxStepsSolution();
        int result = 0;
        for (String key :
                stepIntegerMap.keySet()){
            if (stepIntegerMap.get(key) == Integer.MAX_VALUE){
                System.out.println(-1);
                return;
            }
            result = Math.max(stepIntegerMap.get(key), result);
        }
        System.out.println(result);
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 7.明朝那些事(一)太子的前世今生 为了迷惑明朝,打消明朝的警惕,为自己争取尽可能多的时间,努尔哈赤玩了一个很简单...
    一只支阅读 847评论 1 10
  • 这一周过的其实并不满意,周一、周五,早上没课就睡了一上午睡过去了,周四因为第二天是双十一,几乎一整天都在逛淘宝什么...
    Ymoniwo阅读 168评论 0 0
  • 今天气温很低,感受得到寒冬的气息,北风打在身上,寒气穿透外衣,彻骨。 中午因约了医生,步行前往,经过湖边,看到一个...
    止弌阅读 192评论 0 0
  • 之前使用的是友盟分享5.几的.但是自定义分享一直导致控制器销毁不了.后来友盟集成了6.0版本.我们也开始集成最新的...
    侭情显現阅读 839评论 0 2
  • 之一:当我太把注意力放在自己身上时,我遇到的任何风吹草动都与我发生联系,却不产生不连接! 之二:当...
    Love李木子阅读 370评论 0 2