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

            USACO 2.4 Overfencing


            找出兩個迷宮的出口,然后分別進行dfs,求出到每一個點的最短距離。
            然后對每一個點,求到最短的那個出口的距離,然后再求這個值的最大值即可。
            找出口寫得比較繁瑣。

            #include?<iostream>
            #include?
            <fstream>
            #include?
            <queue>

            using?namespace?std;

            ifstream?fin(
            "maze1.in");
            ofstream?fout(
            "maze1.out");

            #ifdef?_DEBUG
            #define?out?cout
            #define?in?cin
            #else
            #define?out?fout
            #define?in?fin
            #endif

            char?maze[2*100+1][2*38+1];

            bool?visited[100][38];

            int?shortest1[100][38];
            int?shortest2[100][38];

            bool?get_first;
            int?exit1r,exit1c;
            int?exit2r,exit2c;
            int?w,h;

            struct?queue_node{
            ????
            int?i,j,depth;
            ????queue_node(
            int?i,int?j,int?depth){
            ????????
            this->i?=?i;
            ????????
            this->j?=?j;
            ????????
            this->depth?=?depth;
            ????}
            };

            void?bfs(int?i,int?j,int?shortest[100][38])
            {
            ????queue
            <queue_node>q;

            ????q.push(queue_node(i,j,
            1));

            ????
            while(!q.empty()){

            ????????queue_node?node?
            =?q.front();
            ????????q.pop();

            ????????
            if(visited[node.i][node.j])
            ????????????
            continue;

            ????????visited[node.i][node.j]?
            =?true;

            ????????shortest[node.i][node.j]?
            =?node.depth;

            ????????
            if(node.i!=0&&maze[2*node.i][2*node.j+1]=='?'){
            ????????????q.push(queue_node(node.i
            -1,node.j,node.depth+1));
            ????????}
            ????????
            if(node.i!=h-1&&maze[2*node.i+2][2*node.j+1]=='?'){
            ????????????q.push(queue_node(node.i
            +1,node.j,node.depth+1));
            ????????}
            ????????
            if(node.j!=0&&maze[2*node.i+1][2*node.j]=='?'){
            ????????????q.push(queue_node(node.i,node.j
            -1,node.depth+1));
            ????????}
            ????????
            if(node.j!=w-1&&maze[2*node.i+1][2*node.j+2]=='?'){
            ????????????q.push(queue_node(node.i,node.j
            +1,node.depth+1));
            ????????}
            ????}
            }

            void?solve()
            {
            ????
            in>>w>>h;

            ????
            for(int?i=0;i<2*h+1;++i)
            ????????
            for(int?j=0;j<2*w+1;++j){

            ????????????
            do{
            ????????????
            in.get(maze[i][j]);
            ????????????}
            while(maze[i][j]=='\n');

            ????????????
            if((i==0||i==2*h||j==0||j==2*w)&&maze[i][j]=='?'){
            ????????????????
            if(!get_first){
            ????????????????????
            if(i==2*h)
            ????????????????????????exit1r?
            =?h-1;
            ????????????????????
            else
            ????????????????????????exit1r?
            =?i/2;
            ????????????????????
            if(j==2*w)
            ????????????????????????exit1c?
            =?w-1;
            ????????????????????
            else
            ????????????????????????exit1c?
            =?j/2;
            ????????????????????get_first?
            =?true;
            ????????????????}
            else{
            ????????????????????
            if(i==2*h)
            ????????????????????????exit2r?
            =?h-1;
            ????????????????????
            else
            ????????????????????????exit2r?
            =?i/2;
            ????????????????????
            if(j==2*w)
            ????????????????????????exit2c?
            =?w-1;
            ????????????????????
            else
            ????????????????????????exit2c?
            =?j/2;
            ????????????????}
            ????????????}
            ????????}

            ????memset(visited,
            0,sizeof(visited));
            ????bfs(exit1r,exit1c,shortest1);
            ????memset(visited,
            0,sizeof(visited));
            ????bfs(exit2r,exit2c,shortest2);

            ????
            int?res?=?INT_MIN;

            ????
            for(int?i=0;i<h;++i)
            ?????
            for(int?j=0;j<w;++j){
            ?????????res?
            =?max(res,?min(shortest1[i][j],shortest2[i][j])?);
            ?????}

            ????
            out<<res<<endl;
            }

            int?main(int?argc,char?*argv[])
            {
            ????solve();?
            ????
            return?0;
            }



            posted on 2009-06-26 22:25 YZY 閱讀(1255) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO搜索

            導航

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久久久一级精品亚洲国产成人综合AV区 | 久久99精品国产麻豆蜜芽| 久久99精品久久久久久不卡| 91久久国产视频| 精品综合久久久久久97| 精品久久人妻av中文字幕| 国产—久久香蕉国产线看观看| 中文无码久久精品| 久久亚洲欧洲国产综合| 一本久久a久久精品亚洲| 99久久婷婷国产一区二区| 久久久久久久波多野结衣高潮| 久久国产精品-久久精品| 97久久婷婷五月综合色d啪蜜芽| 嫩草影院久久99| 丰满少妇高潮惨叫久久久| 亚洲国产精品嫩草影院久久| 香蕉99久久国产综合精品宅男自 | 国产精品久久久亚洲| 伊人 久久 精品| 久久国产午夜精品一区二区三区| 久久免费高清视频| 久久夜色精品国产噜噜麻豆| 亚洲中文字幕无码久久2017| 国产精品无码久久综合网| 99久久精品费精品国产一区二区| 99久久人妻无码精品系列蜜桃| 日韩精品无码久久一区二区三| 色综合久久88色综合天天| 国内精品久久久久影院优| 久久久精品2019免费观看| 国产91色综合久久免费| 亚洲国产精品无码久久98| 久久99精品国产| av午夜福利一片免费看久久| 久久国产精品一国产精品金尊 | 国产精品无码久久综合| 精品久久久无码人妻中文字幕豆芽| 久久亚洲精品中文字幕| 久久精品蜜芽亚洲国产AV| 国产三级久久久精品麻豆三级|