• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 74,  comments - 33,  trackbacks - 0
            Meteor Shower
            Time Limit: 1000MS Memory Limit: 65536K
            Total Submissions: 2467 Accepted: 676

            Description

            Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

            The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti? ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

            Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

            Determine the minimum time it takes Bessie to get to a safe place.

            Input

            * Line 1: A single integer: M
            * Lines 2..M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti

            Output

            * Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

            Sample Input

            4
            0 0 2
            2 1 2
            1 1 2
            0 3 5
            

            Sample Output

            5
            

            Source

            USACO 2008 February Silver
            這道題沒(méi)什么,一道BFS而已,只是數(shù)據(jù)有點(diǎn)問(wèn)題,看了Discuss才知道有超出300的數(shù)據(jù)我一生氣就開(kāi)了500,開(kāi)始RE,后來(lái)一次AC,唯一值得紀(jì)念的就是用了STL的queue寫(xiě)了BFS,下次看來(lái)要用stack寫(xiě)DFS了的確很是方便,部分代碼如下:
            while(!q.empty()){
            ????????????point
            =q.front();
            ????????????a
            =point.x,b=point.y;
            ????????????
            if(flag[a][b]==0)break;
            ????????????
            for(int?i=0;i<4;i++){
            ????????????????
            int?x=a+dir[i][0];
            ????????????????
            int?y=b+dir[i][1];
            ????????????????
            if(OK(x,y)&&(map[x][y]==0||map[x][y]>map[a][b]+1)){
            ????????????????????
            if(map[x][y])flag[x][y]=1;
            ????????????????????map[x][y]
            =map[a][b]+1;
            ????????????????????point.x
            =x,point.y=y;
            ????????????????????q.push(point);????
            ????????????????}

            ????????????}

            ????????????q.pop();????????
            ????????}

            posted on 2009-03-30 09:50 KNIGHT 閱讀(169) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            九九精品99久久久香蕉| 久久精品国产亚洲AV大全| 精品久久久久久久| 国产精品美女久久久久AV福利 | yellow中文字幕久久网| 国内精品免费久久影院| 97香蕉久久夜色精品国产 | 久久精品视频一| 波多野结衣中文字幕久久| 激情综合色综合久久综合| 久久亚洲日韩看片无码| 久久青草国产手机看片福利盒子| 久久久精品国产免大香伊| 中文字幕成人精品久久不卡| 人妻少妇久久中文字幕| 四虎影视久久久免费| 99精品伊人久久久大香线蕉| 久久久久亚洲精品日久生情 | 亚洲色欲久久久久综合网| 大美女久久久久久j久久| 久久久无码精品亚洲日韩蜜臀浪潮 | 狠狠久久综合| av无码久久久久久不卡网站| 久久久久亚洲国产| 久久99国产一区二区三区| 99久久精品国产麻豆| 成人综合伊人五月婷久久| 精品多毛少妇人妻AV免费久久| 国产AV影片久久久久久| 久久久精品2019免费观看| 国产99久久久国产精品小说| 亚洲第一永久AV网站久久精品男人的天堂AV | 国内精品久久久人妻中文字幕| 狠狠综合久久综合88亚洲| 曰曰摸天天摸人人看久久久| 久久大香香蕉国产| 人妻无码中文久久久久专区| 亚洲第一极品精品无码久久 | 久久精品免费一区二区| 99久久国产亚洲综合精品| 亚洲欧美成人久久综合中文网 |