• <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>
            posts - 33,  comments - 33,  trackbacks - 0
            大意:給出一個區域圖和Click的坐標,求擊中區域的周長
            題解:爆搜,BFS出整個連通域,注意求周長是上下左右的連通域,所以將8連域分成兩個4連域,然后在BFS時一并計算出周長
            代碼:
            #include <stdio.h>
            #include 
            <queue>
            using namespace std;

            const int dsx1[4= {1,0,-1,0};
            const int dsy1[4= {0,1,0,-1};
            const int dsx2[4= {1,-1,-1,1};
            const int dsy2[4= {1,1,-1,-1};

            int width;
            int height;
            int startX,startY;
            char Maps[25][25];
            bool visited[25][25];

            const bool bound(int _x,int _y)
            {
                
            return (_x >=0 && _x < width)&&(_y >= 0 && _y < height);
            }


            int BFS()
            {
                
            int ret = 0;
                
            if (Maps[startY][startX] !='X')
                
            {
                    
            return 0;
                }

                memset(visited,
            0,sizeof(visited));
                queue
            <int> que;
                que.push(startY
            *100 + startX);
                visited[startY][startX] 
            = true;
                
            while(!que.empty())
                
            {
                    
            int curId = que.front();
                    que.pop();
                    
            int curX = curId % 100;
                    
            int curY = curId / 100;
                    
            int newX,newY;
                    
            for (int i = 0; i < 4++i)
                    
            {
                        newX 
            = curX + dsx1[i];
                        newY 
            = curY + dsy1[i];
                        
            if (bound(newX,newY))
                        
            {
                            
            if (!visited[newY][newX])
                            
            {    
                                
            if (Maps[newY][newX] == 'X')
                                
            {
                                    visited[newY][newX] 
            = true;
                                    que.push(newY
            *100 + newX);
                                }

                                
            else
                                
            {
                                    
            //add
                                    ++ret;
                                }

                            }

                        }

                        
            else
                        
            {
                            
            ++ret;
                        }

                    }

                    
            for (int i = 0; i < 4++i)
                    
            {
                        newX 
            = curX + dsx2[i];
                        newY 
            = curY + dsy2[i];
                        
            if (bound(newX,newY))
                        
            {
                            
            if (!visited[newY][newX])
                            
            {        
                                
            if (Maps[newY][newX] == 'X')
                                
            {
                                    
                                    visited[newY][newX] 
            = true;
                                    que.push(newY
            *100 + newX);
                                }

                            }

                        }

                    }

                }

                
            return ret;
            }


            void Test()
            {
                memset(Maps,
            0,sizeof(Maps));
                
            for (int i = 0; i < height; ++i)
                
            {
                    scanf(
            "%s",Maps[i]);
                }

                printf(
            "%d\n",BFS());
            }


            int main()
            {
                
            //freopen("data.txt","r",stdin);
                while(scanf("%d %d %d %d",&height,&width,&startY,&startX) != EOF)
                
            {
                    
            if (height == 0)
                    
            {
                        
            break;
                    }

                    
            --startY;
                    
            --startX;
                    Test();
                }

                
            return 0;
            }


            posted on 2011-11-09 12:34 bennycen 閱讀(1508) 評論(1)  編輯 收藏 引用 所屬分類: 算法題解
            欧美精品久久久久久久自慰| 久久久久久国产精品美女| 久久频这里精品99香蕉久| 一本久久免费视频| 欧美一区二区三区久久综| 热久久这里只有精品| 国产香蕉久久精品综合网| 伊人久久无码中文字幕| 狠狠色丁香婷婷综合久久来| 精品综合久久久久久88小说| 一本色道久久88—综合亚洲精品| 欧美亚洲国产精品久久蜜芽| 无码人妻久久一区二区三区蜜桃| 亚洲精品tv久久久久久久久| 99久久国产综合精品五月天喷水| 国色天香久久久久久久小说| 久久99国产精品二区不卡| 久久亚洲日韩看片无码| 精品久久久久久久久久中文字幕| 婷婷久久久亚洲欧洲日产国码AV | 影音先锋女人AV鲁色资源网久久 | 18岁日韩内射颜射午夜久久成人| 久久精品国产亚洲网站| 亚洲va久久久噜噜噜久久狠狠| 久久久久亚洲精品天堂久久久久久 | 国产精品热久久无码av| 午夜久久久久久禁播电影| 无码任你躁久久久久久老妇| 久久精品国产福利国产秒| 99久久婷婷国产综合亚洲| 久久国产欧美日韩精品| 伊人久久亚洲综合影院| 三级片免费观看久久| 久久精品国产亚洲Aⅴ蜜臀色欲| 久久国产精品成人免费| 狠狠色丁香久久综合婷婷| 国产综合久久久久| 久久免费小视频| 97超级碰碰碰碰久久久久| 91亚洲国产成人久久精品网址| 国产福利电影一区二区三区久久久久成人精品综合 |