• <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>

            pku 3501 Escape from Enemy Territory 二分+BFS

            題意:
            網格圖上有N個敵人的據點。求從起點到終點路徑中到敵人據點Manhattan distance: dist((x1, y1), (x2, y2)) = |x2x1| + |y2y1|. 最長距離,如果有重復,則使得路徑長度最短。
            解法:
            二分路徑中到敵人據點的最短距離,然后用BFS check
            注意在chk時可以開個bool數組來標記,不用標記到所有的不合法點,只要標記其輪廓就可以了,這樣可以降低復雜度的階
            代碼:
             1# include <cstdio>
             2# include <cstring>
             3using namespace std;
             4int n,w,h,sx,sy,ex,ey;
             5int p[10001][2];
             6int q[1000005][2];
             7int map[1001][1001];
             8# define abs(a) ((a)>0?(a):-(a))
             9# define legal(a,b) ((a)>=0&&(a)<w&&(b)>=0&&(b)<h)
            10int chk(int limit)
            11{
            12    memset(map,-1,sizeof(map));
            13    for(int i=0;i<n;i++)
            14        for(int l=0;l<=limit;l++)
            15        {
            16            if(legal(p[i][0]-l,p[i][1]+limit-l))
            17               map[p[i][0]-l][p[i][1]+limit-l]=-2;
            18            if(legal(p[i][0]+l,p[i][1]+limit-l))
            19               map[p[i][0]+l][p[i][1]+limit-l]=-2;
            20            if(legal(p[i][0]-l,p[i][1]-limit+l))
            21               map[p[i][0]-l][p[i][1]-limit+l]=-2;
            22            if(legal(p[i][0]+l,p[i][1]-limit+l))
            23               map[p[i][0]+l][p[i][1]-limit+l]=-2;
            24        }

            25    for(int i=0;i<n;i++)
            26      if(abs(p[i][0]-sx)+abs(p[i][1]-sy)<=limit||abs(p[i][0]-ex)+abs(p[i][1]-ey)<=limit) return -1;
            27    int s=-1,e=-1;
            28    e++;
            29    q[e][0]=sx;
            30    q[e][1]=sy;
            31    map[sx][sy]=0;
            32    while(s!=e)
            33    {
            34       s++;
            35       int x=q[s][0],y=q[s][1];
            36       if(legal(x-1,y)&&map[x-1][y]==-1)
            37       {
            38         e++;
            39         q[e][0]=x-1;
            40         q[e][1]=y;
            41         map[q[e][0]][q[e][1]]=map[x][y]+1;
            42       }

            43       if(legal(x+1,y)&&map[x+1][y]==-1)
            44       {
            45         e++;
            46         q[e][0]=x+1;
            47         q[e][1]=y;
            48         map[q[e][0]][q[e][1]]=map[x][y]+1;
            49       }

            50       if(legal(x,y-1)&&map[x][y-1]==-1)
            51       {
            52         e++;
            53         q[e][0]=x;
            54         q[e][1]=y-1;
            55         map[q[e][0]][q[e][1]]=map[x][y]+1;
            56       }

            57       if(legal(x,y+1)&&map[x][y+1]==-1)
            58       {
            59         e++;
            60         q[e][0]=x;
            61         q[e][1]=y+1;
            62         map[q[e][0]][q[e][1]]=map[x][y]+1;
            63       }

            64    }

            65    return map[ex][ey]==-2||map[ex][ey]==-1?-1:map[ex][ey];
            66}

            67int main()
            68{
            69    int test;
            70    scanf("%d",&test);
            71    while(test--)
            72    {
            73        scanf("%d%d%d%d%d%d%d",&n,&w,&h,&sx,&sy,&ex,&ey);
            74        for(int i=0;i<n;i++)
            75          scanf("%d%d",&p[i][0],&p[i][1]);
            76        int s=0,e=(w>h?w:h)-1;
            77        while(s<=e)
            78        {
            79           int mid=(s+e)>>1;
            80           if(chk(mid)!=-1) s=mid+1;
            81           else e=mid-1;
            82        }

            83        printf("%d %d\n",e+1,chk(e));
            84    }
                
            85    return 0;
            86}

            87

            posted on 2010-12-02 22:47 yzhw 閱讀(270) 評論(0)  編輯 收藏 引用 所屬分類: search

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久99精品国产99久久| 丁香色欲久久久久久综合网| 国产99精品久久| 国产成人久久777777| 性高朝久久久久久久久久| 久久久无码精品亚洲日韩京东传媒| 久久夜色精品国产欧美乱| 国产精品欧美久久久久天天影视 | 久久久久久久久久久久久久| 久久精品99久久香蕉国产色戒 | 2021精品国产综合久久| 久久男人中文字幕资源站| 亚洲香蕉网久久综合影视| 91久久香蕉国产熟女线看| 亚洲精品无码久久千人斩| 久久久中文字幕日本| AAA级久久久精品无码区| 久久亚洲日韩精品一区二区三区| 久久久久国产一区二区| 99久久久精品| 国产精品久久久久国产A级| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 天天躁日日躁狠狠久久 | 久久久久99精品成人片直播| 色诱久久av| 久久中文字幕视频、最近更新| 久久国产精品成人免费| 久久精品国产亚洲AV香蕉| 久久精品国产亚洲AV蜜臀色欲| 亚洲精品综合久久| 久久青青草原精品国产不卡| 精品久久久久久久中文字幕| 久久综合九色综合97_久久久| 久久精品国产清高在天天线| 久久99国产精品尤物| 日韩人妻无码精品久久免费一| 中文字幕久久精品无码| 伊人久久综合精品无码AV专区| 国产激情久久久久久熟女老人| 中文精品久久久久人妻不卡| 久久久久亚洲av无码专区导航 |