• <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 閱讀(168) 評(píng)論(0)  編輯 收藏 引用

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


            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久久一本毛久久久| 色综合久久中文字幕综合网| 少妇人妻综合久久中文字幕| 亚洲精品WWW久久久久久| 久久精品国产2020| 狠狠色婷婷久久一区二区三区 | 亚洲va久久久噜噜噜久久天堂| 国产精品99久久久精品无码| 伊人久久大香线蕉av一区| 日本欧美久久久久免费播放网| 99久久无码一区人妻a黑| 久久男人中文字幕资源站| 亚洲国产精品无码久久一区二区| 久久这里只有精品18| 久久精品国产色蜜蜜麻豆| 亚洲αv久久久噜噜噜噜噜| 久久99热精品| 午夜天堂精品久久久久| 久久综合五月丁香久久激情| 婷婷久久久亚洲欧洲日产国码AV | 99久久中文字幕| 一级做a爰片久久毛片免费陪| av国内精品久久久久影院| 欧美麻豆久久久久久中文| 国产精品一区二区久久| 欧美一区二区久久精品| 大蕉久久伊人中文字幕| 亚洲精品无码成人片久久| 久久综合伊人77777麻豆| 久久成人影院精品777| 亚洲愉拍99热成人精品热久久| 国产精品日韩深夜福利久久| 久久成人国产精品| 欧洲人妻丰满av无码久久不卡 | 国内精品久久国产| 久久精品这里只有精99品| 热re99久久精品国产99热| 国产亚洲精品自在久久| 狠狠综合久久综合88亚洲| 伊人久久大香线蕉精品不卡| 精品久久综合1区2区3区激情|