網(wǎng)易牢籠問題 70%

網(wǎng)易大哥請告訴我哪里是出口?

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);
    }
}

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市渐夸,隨后出現(xiàn)的幾起案子摧冀,更是在濱河造成了極大的恐慌,老刑警劉巖其做,帶你破解...
    沈念sama閱讀 221,635評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件菩彬,死亡現(xiàn)場離奇詭異,居然都是意外死亡沼溜,警方通過查閱死者的電腦和手機平挑,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,543評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來系草,“玉大人通熄,你說我怎么就攤上這事≌叶迹” “怎么了唇辨?”我有些...
    開封第一講書人閱讀 168,083評論 0 360
  • 文/不壞的土叔 我叫張陵,是天一觀的道長能耻。 經常有香客問我赏枚,道長,這世上最難降的妖魔是什么晓猛? 我笑而不...
    開封第一講書人閱讀 59,640評論 1 296
  • 正文 為了忘掉前任饿幅,我火速辦了婚禮,結果婚禮上戒职,老公的妹妹穿的比我還像新娘栗恩。我一直安慰自己,他們只是感情好洪燥,可當我...
    茶點故事閱讀 68,640評論 6 397
  • 文/花漫 我一把揭開白布摄凡。 她就那樣靜靜地躺著,像睡著了一般蚓曼。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上钦扭,一...
    開封第一講書人閱讀 52,262評論 1 308
  • 那天纫版,我揣著相機與錄音,去河邊找鬼客情。 笑死其弊,一個胖子當著我的面吹牛,可吹牛的內容都是我干的膀斋。 我是一名探鬼主播梭伐,決...
    沈念sama閱讀 40,833評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼仰担!你這毒婦竟也來了糊识?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 39,736評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎赂苗,沒想到半個月后愉耙,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經...
    沈念sama閱讀 46,280評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡拌滋,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,369評論 3 340
  • 正文 我和宋清朗相戀三年朴沿,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片败砂。...
    茶點故事閱讀 40,503評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡赌渣,死狀恐怖,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情止潮,我是刑警寧澤题画,帶...
    沈念sama閱讀 36,185評論 5 350
  • 正文 年R本政府宣布,位于F島的核電站货岭,受9級特大地震影響,放射性物質發(fā)生泄漏疾渴。R本人自食惡果不足惜千贯,卻給世界環(huán)境...
    茶點故事閱讀 41,870評論 3 333
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望搞坝。 院中可真熱鬧搔谴,春花似錦、人聲如沸桩撮。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,340評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽店量。三九已至芜果,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間融师,已是汗流浹背右钾。 一陣腳步聲響...
    開封第一講書人閱讀 33,460評論 1 272
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留旱爆,地道東北人舀射。 一個月前我還...
    沈念sama閱讀 48,909評論 3 376
  • 正文 我出身青樓,卻偏偏與公主長得像怀伦,于是被迫代替她去往敵國和親脆烟。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,512評論 2 359

推薦閱讀更多精彩內容

  • 7.明朝那些事(一)太子的前世今生 為了迷惑明朝房待,打消明朝的警惕邢羔,為自己爭取盡可能多的時間驼抹,努爾哈赤玩了一個很簡單...
    一只支閱讀 837評論 1 10
  • 這一周過的其實并不滿意,周一张抄、周五砂蔽,早上沒課就睡了一上午睡過去了,周四因為第二天是雙十一署惯,幾乎一整天都在逛淘寶什么...
    Ymoniwo閱讀 156評論 0 0
  • 今天氣溫很低左驾,感受得到寒冬的氣息,北風打在身上极谊,寒氣穿透外衣诡右,徹骨。 中午因約了醫(yī)生轻猖,步行前往帆吻,經過湖邊,看到一個...
    止弌閱讀 176評論 0 0
  • 之前使用的是友盟分享5.幾的.但是自定義分享一直導致控制器銷毀不了.后來友盟集成了6.0版本.我們也開始集成最新的...
    侭情顯現(xiàn)閱讀 828評論 0 2
  • 之一:當我太把注意力放在自己身上時咙边,我遇到的任何風吹草動都與我發(fā)生聯(lián)系猜煮,卻不產生不連接! 之二:當...
    Love李木子閱讀 363評論 0 2