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

            lzm

            who dare win.
            posts - 14, comments - 29, trackbacks - 0, articles - 0

            poj 1024 Tester Program

            Posted on 2009-03-19 08:59 lzmagic 閱讀(949) 評論(1)  編輯 收藏 引用 所屬分類: OJ
            /**
             * (1)求各點(diǎn)到源點(diǎn)的最小步數(shù)(BFS)
             * (2)求各點(diǎn)到終點(diǎn)的最小步數(shù)(BFS)
             * (3)如果點(diǎn)不是給定路徑上的點(diǎn),那么:該點(diǎn)到源點(diǎn)的最小步數(shù)+該點(diǎn)到終點(diǎn)的最小步數(shù)<給定路徑的步數(shù),否則給定路徑不是唯一最短的
             * (4)如果兩相鄰點(diǎn)a、b之間存在墻,那么:a到源點(diǎn)的最小步數(shù)+1+b到終點(diǎn)的最小步數(shù)<=給定路徑的步數(shù)
             *                              或者 a到終點(diǎn)的最小步數(shù)+1+b到源點(diǎn)的最小步數(shù)<=給定路徑的步數(shù),否則墻多余
             * (5)如果存在點(diǎn)不可達(dá),說明存在墻將該點(diǎn)封閉起來,可以證明墻至少有一塊多余
             
            */
            #include 
            <iostream>
            #include 
            <string>
            #include 
            <queue>
            using namespace std;

            struct Grid
            {
                
            bool inpath;    // 是否是路徑方格
                bool uwal;      // 是否有上墻
                bool rwal;      // 是否有右墻
                int scnt;       // 到源點(diǎn)步數(shù)
                int dcnt;       // 到終點(diǎn)步數(shù)
            };

            int main(int argc, char** argv)
            {
                
            bool ok;
                
            int w, h, cnt, steps;   // 1 <= w, h <= 100
                string path;
                Grid grid[
            100][100];
                queue
            <pair<intint> > q;

                
            int t, x, y, desx, desy, x2, y2, i;
                
            for (cin >> t; t > 0--t)
                {
                    
            // 初始化數(shù)據(jù)
                    cin >> w >> h;
                    
            for (y = 0; y < h; ++y)
                        
            for (x = 0; x < w; ++x)
                        {
                            grid[y][x].inpath 
            = false;
                            grid[y][x].uwal 
            = false;
                            grid[y][x].rwal 
            = false;
                            grid[y][x].scnt 
            = -1;
                            grid[y][x].dcnt 
            = -1;
                        }
                    cin 
            >> path;
                    x 
            = 0, y = 0;
                    grid[
            0][0].inpath = true;
                    steps 
            = path.size();
                    
            for (i = 0; i < steps; ++i)
                    {
                        
            switch(path[i])
                        {
                            
            case 'U'++y; break;
                            
            case 'D'--y; break;
                            
            case 'L'--x; break;
                            
            case 'R'++x; break;
                        }
                        grid[y][x].inpath 
            = true;
                    }
                    desx 
            = x, desy = y;
                    cin 
            >> cnt;
                    
            for (i = 0; i < cnt; ++i)
                    {
                        cin 
            >> x >> y >> x2 >> y2;
                        
            if (x == x2)
                            
            if (y + 1 == y2) grid[y][x].uwal = true;
                            
            else grid[y2][x].uwal = true;
                        
            else
                            
            if (x + 1 == x2) grid[y][x].rwal = true;
                            
            else grid[y][x2].rwal = true;
                    }

                    
            // 求各點(diǎn)到源點(diǎn)的最小步數(shù)(BFS)
                    q.push(make_pair(00));
                    grid[
            0][0].scnt = 0;
                    
            while (!q.empty())
                    {
                        y 
            = q.front().first, x = q.front().second;
                        
            if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].scnt == -1)
                        {
                            grid[y 
            + 1][x].scnt = grid[y][x].scnt + 1;
                            q.push(make_pair(y 
            + 1, x));
                        }
                        
            if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].scnt == -1)
                        {
                            grid[y 
            - 1][x].scnt = grid[y][x].scnt + 1;
                            q.push(make_pair(y 
            - 1, x));
                        }
                        
            if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].scnt == -1)
                        {
                            grid[y][x 
            - 1].scnt = grid[y][x].scnt + 1;
                            q.push(make_pair(y, x 
            - 1));
                        }
                        
            if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].scnt == -1)
                        {
                            grid[y][x 
            + 1].scnt = grid[y][x].scnt + 1;
                            q.push(make_pair(y, x 
            + 1));
                        }
                        q.pop();
                    }

                    
            // 求各點(diǎn)到終點(diǎn)的最小步數(shù)(BFS)
                    q.push(make_pair(desy, desx));
                    grid[desy][desx].dcnt 
            = 0;
                    
            while (!q.empty())
                    {
                        y 
            = q.front().first, x = q.front().second;
                        
            if (y < h - 1 && grid[y][x].uwal == false && grid[y + 1][x].dcnt == -1)
                        {
                            grid[y 
            + 1][x].dcnt = grid[y][x].dcnt + 1;
                            q.push(make_pair(y 
            + 1, x));
                        }
                        
            if (0 < y && grid[y - 1][x].uwal == false && grid[y - 1][x].dcnt == -1)
                        {
                            grid[y 
            - 1][x].dcnt = grid[y][x].dcnt + 1;
                            q.push(make_pair(y 
            - 1, x));
                        }
                        
            if (0 < x && grid[y][x - 1].rwal == false && grid[y][x - 1].dcnt == -1)
                        {
                            grid[y][x 
            - 1].dcnt = grid[y][x].dcnt + 1;
                            q.push(make_pair(y, x 
            - 1));
                        }
                        
            if (x < w - 1 && grid[y][x].rwal == false && grid[y][x + 1].dcnt == -1)
                        {
                            grid[y][x 
            + 1].dcnt = grid[y][x].dcnt + 1;
                            q.push(make_pair(y, x 
            + 1));
                        }
                        q.pop();
                    }

                    
            // 判斷路徑是否唯一最短,以及墻是否多余
                    ok = true;
                    
            for (y = 0; y < h && ok; ++y)
                        
            for (x = 0; x < w && ok; ++x)
                        {
                            
            if (grid[y][x].scnt == -1 || grid[y][x].dcnt == -1)
                                ok 
            = false;     // 是否有封閉區(qū)域
                            if (y < h - 1 && grid[y][x].uwal
                                    
            && grid[y][x].scnt + grid[y + 1][x].dcnt + 1 > steps
                                    
            && grid[y][x].dcnt + grid[y + 1][x].scnt + 1 > steps)
                                ok 
            = false;     // 是否上墻多余
                            if (x < w - 1 && grid[y][x].rwal
                                    
            && grid[y][x].scnt + grid[y][x + 1].dcnt + 1 > steps
                                    
            && grid[y][x].dcnt + grid[y][x + 1].scnt + 1 > steps)
                                ok 
            = false;     // 是否右墻多余
                            if (!grid[y][x].inpath && grid[y][x].scnt + grid[y][x].dcnt <= steps)
                                ok 
            = false;     // 是否存在更短路徑或另一最短路徑
                        }
                    
            if(ok) cout << "CORRECT" << endl;
                    
            else cout << "INCORRECT" << endl;
                }

                
            return 0;
            }



            Feedback

            # re: poj 1024 Tester Program[未登錄]  回復(fù)  更多評論   

            2010-01-15 22:08 by joy
            灰常感謝LZ,看了你的第5條那個(gè),讓debug了3個(gè)小時(shí)的我一下就過了;
            因?yàn)槲业某跏蓟瓉硎?1,所以釀成杯具啊。。
            這bug。。汗。
            日韩精品久久久久久久电影蜜臀| 99久久精品国产综合一区 | 久久天天躁狠狠躁夜夜躁2014| 性做久久久久久免费观看| 亚洲国产成人久久综合碰| 人妻精品久久无码区| 精品无码久久久久久久动漫| 国产精品美女久久福利网站| 国产精品99精品久久免费| 欧美日韩精品久久久免费观看| 久久99精品久久久久久久久久| 91麻精品国产91久久久久| 亚洲AV日韩精品久久久久| 久久精品亚洲乱码伦伦中文| 午夜久久久久久禁播电影| 久久人人爽人人精品视频| 精品久久一区二区三区| 久久天堂AV综合合色蜜桃网| 午夜精品久久久久9999高清| 国产福利电影一区二区三区久久久久成人精品综合| 日本高清无卡码一区二区久久 | 狠狠色丁香久久婷婷综合图片| 国产亚洲美女精品久久久久狼| 狠狠色狠狠色综合久久| 伊人色综合久久天天网| 国产精自产拍久久久久久蜜| 久久久久免费精品国产| 99精品国产在热久久无毒不卡| 久久人人爽人人爽人人片AV高清| 欧美大战日韩91综合一区婷婷久久青草| 狠色狠色狠狠色综合久久| 精品久久久久久无码中文字幕一区 | 一本色道久久88综合日韩精品 | 亚洲中文字幕久久精品无码喷水| 亚洲精品无码久久久| 伊人色综合久久天天网 | 久久99精品国产自在现线小黄鸭 | 久久99精品九九九久久婷婷| 国产精品久久久久影院色| 久久国产色AV免费观看| 97久久香蕉国产线看观看|