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

            The Fourth Dimension Space

            枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

            POJ 1111-Image Perimeters DFS深度優先搜索

            以前做過POJ上的3620,題意大概是要你求出相鄰的X有多少個,而這個題呢,則是要求你求出整個互相鄰接的X所夠成的周長;
            我個人認為,這兩道題有異曲同工之妙。
            這道題和3620不同的是,我們不能將所有與X相鄰的結點都壓棧,而是選擇X結點壓棧,為什么呢?我想了想,因為此題的周長是在你考察X的基礎上向四面八方試探而求出的。你最好是立足與X結點,由于對壓棧元素進行了限制,那么在進入dfs遞歸的時候也就不用大費周章的去判斷
            if(visit[i][j]==0)了,因為壓棧的元素必須是沒有考察過的X結點;當然這只不過是基于自己的個人習慣而已,我想,即使你不判斷壓棧元素,應該也能做出來吧,只不過這樣似乎并不符合我們的思維習慣而已;
            另外做這個題目的時候還遇到了一個小問題,就是cin.ignore()的使用,再輸入r,c,x,y的值之后,由于回車符不可能被整型變量吃掉,所以它會滯留在緩沖區,使得在輸入字符時回車符優先進入map數組,而且每一行之后都有一個回車符,所以這個cin.ignore()的位置也是不能改變的。
            當讓還有個有意思的地方,就是這個題要用向量來存儲考察的方向,這樣的話一個循環就可以考察完所有的方向,不用費力把所有的方向都寫一遍了,這是一個很不錯的方法,宜借鑒之;
            最后要感謝一下網路上分享代碼的大牛們,正是由于參考了你們的代碼才使我有所進步;

            #include<iostream>
            #include
            <cmath>
            #include
            <cstdio>
            using namespace std;
            #define MAX 100

            char map[MAX][MAX];
            int visit[MAX][MAX];
            int sum;
            int r,c;
            int path[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};



            void dfs(int a,int b)
            {

                visit[a][b]
            =1;
                
            int i;
                
            for(i=0;i<8;i++)
                
            {
                    
            int x=a+path[i][0];
                    
            int y=b+path[i][1];

                    
            if(x>=1&&x<=r&&y>=1&&y<=c)
                    
            {

                        
            if(map[x][y]=='X'&&visit[x][y]==0)
                            dfs(x,y);
                            
                        
            else if(map[x][y]=='.'&&(x==a||y==b))
                        
            {
                            sum
            ++;

                        }


                    }

                    
            else if(x==a||y==b)
                        sum
            ++;
                }


            }



            int main ()

            {

                
            int x,y;
                
            int i,j;
                
            while(scanf("%d%d%d%d",&r,&c,&x,&y))
                
            {
                    
            for(i=1;i<=r;i++)
                        
            for(j=1;j<=c;j++)
                        
            {

                            visit[i][j]
            =0;
                        }

                    
                    
            for(i=1;i<=r;i++)
                    
            {
                        cin.ignore();
                        
            for(j=1;j<=c;j++)
                        
            {
                            scanf(
            "%c",&map[i][j]);
                        }


                    }

                    
                    sum
            =0;
                    
            if(r==0&&c==0&&x==0&&y==0)
                        
            break;
                    dfs(x,y);
                    printf(
            "%d\n",sum);
                }

            return 0;
            }




             

            posted on 2009-03-12 20:47 abilitytao 閱讀(1911) 評論(1)  編輯 收藏 引用

            評論

            # re: POJ 1111-Image Perimeters DFS深度優先搜索 2009-07-09 11:12 非要有姓名嗎

            題目好像有小問題。根據題目所給的條件(沒有完全封閉的內孔)也可以邊界追蹤的。經試驗,WA。  回復  更多評論   

            亚洲国产一成人久久精品| 国产精品成人久久久久久久| 久久久久久国产a免费观看不卡| 波多野结衣中文字幕久久| A级毛片无码久久精品免费| 伊人久久综合无码成人网| 久久人与动人物a级毛片| 亚洲乱码精品久久久久..| 亚洲第一极品精品无码久久| 色婷婷综合久久久久中文一区二区| 久久天天躁夜夜躁狠狠| 久久亚洲私人国产精品| 精品亚洲综合久久中文字幕| 99久久精品免费观看国产| 久久国产香蕉视频| 久久婷婷五月综合97色直播 | 精品国产青草久久久久福利| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 国产精品久久久香蕉| 无码日韩人妻精品久久蜜桃| 国内精品伊人久久久久AV影院| 久久久精品午夜免费不卡| 久久国产午夜精品一区二区三区| 中文字幕久久精品| 久久精品国产亚洲AV无码娇色 | 久久久精品人妻无码专区不卡| 久久亚洲国产成人影院| 99久久99久久久精品齐齐| 国内精品欧美久久精品| 精品国产青草久久久久福利| 久久99国产精品99久久| 伊人久久成人成综合网222| 99久久精品国产高清一区二区| 久久久久久亚洲精品不卡| 久久亚洲精品国产精品| 合区精品久久久中文字幕一区| 奇米综合四色77777久久| 欧美久久亚洲精品| 欧美777精品久久久久网| 亚洲国产精品成人久久| 日日狠狠久久偷偷色综合免费 |