• <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>
            深度優先搜索加回溯。之前用四叉樹的記錄遍歷迷宮的所有路徑,結果內存超限制了,請教學長之后才知道有種算法設計方法叫“回溯”,即在沿一條路深度遍歷后再把走過的路標記回來,這樣就能避免影響其它路徑的遍歷。
            另外關于遞歸要說一點,當遞歸中涉及到對全局變量(比如一個全局的數組)的修改時,之前我一直存在的疑問是:如果遞歸式樹狀調用結構,那么每一時刻這個全局的數組在被誰使用呢?如果每層遞歸都能同時使用該數組,那數據不就亂了嗎?原來雖然遞歸的調用可以是樹狀的,但是每一個時刻遞歸都是沿著遞歸樹中的一條路在走,一條路走不通了才會退一步,換個子樹接著走。這些都是在了解回溯之后才想通的。
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            typedef 
            struct 
            {
                
            char x;
                
            char y;
            }
            Node;

            int fd;//have find given length 
            int T;
            int len;
            char mp[8][8];//map
            void f(int x, int y)
            {
                
            if(!fd)
                
            {
                    
            if(mp[x - 1][y] == 'D' && len + 1 == T)fd = 1;
                    
            else if(mp[x - 1][y] == '.')//go up
                    {
                        len 
            ++;
                        mp[x 
            - 1][y] = 'X';
                        f(x 
            - 1, y);
                        len 
            --;
                        mp[x 
            - 1][y] = '.';
                    }

                    
            if(mp[x][y + 1== 'D' && len + 1 == T)fd = 1;
                    
            else if(mp[x][y + 1== '.')//go right
                    {
                        len 
            ++;
                        mp[x][y 
            + 1= 'X';
                        f(x, y 
            + 1);
                        len 
            --;
                        mp[x][y 
            + 1= '.';
                    }

                    
            if(mp[x + 1][y] == 'D' && len + 1 == T)fd = 1;
                    
            else if(mp[x + 1][y] == '.')//go down
                    {
                        len 
            ++;
                        mp[x 
            + 1][y] = 'X';
                        f(x 
            + 1, y);
                        len 
            --;
                        mp[x 
            + 1][y] = '.';
                    }

                    
            if(mp[x][y - 1== 'D' && len + 1 == T)fd = 1;
                    
            else if(mp[x][y - 1== '.')//go left
                    {
                        len 
            ++;
                        mp[x][y 
            - 1= 'X';
                        f(x, y 
            - 1);
                        len 
            --;
                        mp[x][y 
            - 1= '.';
                    }

                }

            }

            int main()
            {
                
            int N, M;
                
            int i, j;
                
            int find;
                Node s;
                scanf(
            "%d%d%d"& N, & M, & T);           
                
            while(N + M + T != 0)
                
            {
                    
            for(i = 1; i <= N; i++)//read map
                        scanf("%s",&mp[i][1]);
                    
            for(i = 1; i <= N; i++)
                        
            for(j = 1; j <= M; j++)
                            
            if(mp[i][j] == 'X')
                        
                    
            for(i = 0; i <= N + 1; i++)//init map
                        mp[i][0= mp[i][M + 1= 'X';    
                    
            for(i = 1; i <= M; i++)
                        mp[
            0][i] = mp[N + 1][i] = 'X';
                        
                    find 
            = 0;
                    
            for(i = 1; i <= N && find == 0; i++)//search start point
                        for(j = 1; j<= M && find == 0; j++)
                            
            if(mp[i][j] == 'S')
                            
            {
                                s.x 
            = i;
                                s.y 
            = j;
                                find 
            = 1;
                            }
             
                            
                    fd 
            = 0;
                    len 
            = 0;
                    f(s.x, s.y);
                    
            if(fd == 1)
                        puts(
            "YES");
                    
            else
                        puts(
            "NO");
                     
                    scanf(
            "%d%d%d"& N, & M, & T);
                }

            }


            posted on 2012-02-28 17:14 小鼠標 閱讀(229) 評論(0)  編輯 收藏 引用
            <2012年2月>
            2930311234
            567891011
            12131415161718
            19202122232425
            26272829123
            45678910

            常用鏈接

            隨筆分類(111)

            隨筆檔案(127)

            friends

            最新評論

            • 1.?re: 線段樹
            • 是這個樣子的,所以在OJ有時候“卡住”了也不要太灰心,沒準真的不是自己的原因呢。
              加油,祝你好運啦!
            • --小鼠標
            • 2.?re: 線段樹
            • 對于編程競賽來說,Java所需時間一般為C/C++的兩倍。合理的競賽給Java的時間限制是給C/C++的兩倍。
            • --傷心的筆
            • 3.?re: poj1273--網絡流
            • 過來看看你。
            • --achiberx
            • 4.?re: (轉)ubuntu11.10無法啟動無線網絡的解決方法
            • 膜拜大神。。查了一個下午資料終于在這里解決了問題。。神牛說的區域賽難道是ACM區域賽。。?
            • --Hang
            • 5.?re: 快速排序、線性時間選擇
            • 博主,謝謝你的文章。你的方法可以很好的處理分區基準在數組中重復的情況,書上的方法遇到這種輸入會堆棧溢出。書上給出了解釋但給的方法貌似不簡潔。
            • --lsxqw2004

            閱讀排行榜

            久久综合五月丁香久久激情| 中文精品99久久国产| 久久亚洲AV成人无码电影| 欧洲精品久久久av无码电影| 久久精品国产亚洲AV电影| 久久免费高清视频| 人妻丰满?V无码久久不卡| 久久综合国产乱子伦精品免费| 国产精品久久久久影院嫩草| Xx性欧美肥妇精品久久久久久| 久久久这里有精品| 久久婷婷久久一区二区三区| 久久久午夜精品福利内容| 97久久超碰成人精品网站| 日韩欧美亚洲综合久久影院Ds| 久久精品九九亚洲精品| 日日狠狠久久偷偷色综合0| 久久精品亚洲精品国产色婷| 婷婷国产天堂久久综合五月| 99久久精品免费国产大片| 奇米综合四色77777久久| 亚洲欧美久久久久9999 | 日韩人妻无码一区二区三区久久 | 久久亚洲精品国产亚洲老地址| 久久99热只有频精品8| 久久亚洲精品国产亚洲老地址| 国产三级观看久久| 久久99精品国产99久久| 久久久久无码精品国产不卡| 久久精品日日躁夜夜躁欧美| 久久伊人五月天论坛| 久久人人爽人人爽人人片AV麻豆 | 久久婷婷人人澡人人| 国产精品久久国产精麻豆99网站| 亚洲精品美女久久久久99| 久久久久久国产精品无码下载| 久久综合久久鬼色| 日日狠狠久久偷偷色综合96蜜桃| 国产精品美女久久久久av爽| 99热精品久久只有精品| 国产高清美女一级a毛片久久w|