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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            2011搜索-題,DFS,類似計算連通區域的個數

            代碼:
            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define MAX_NUM 100
            #define VALID(x, y) ((x)>=0 && (x)<m && (y)>=0 && (y)<n)
            int m, n, count;
            char grid[MAX_NUM][MAX_NUM+1];
            char visited[MAX_NUM][MAX_NUM+1];

            const int dx[] = {-1-1-100111};
            const int dy[] = {-101-11-101};
            void
            dfs_inner(
            int x, int y)
            {
                
            int i, next_x, next_y;
                visited[x][y] 
            = 1;
                
            for(i=0; i<8++i) {
                    next_x 
            = x + dx[i];
                    next_y 
            = y + dy[i];
                    
            if(VALID(next_x, next_y) && !visited[next_x][next_y] &&
                            grid[next_x][next_y]
            =='@')
                        dfs_inner(next_x, next_y);
                }
            }

            void
            dfs()
            {
                
            int i, j;
                
            for(i=0; i<m; ++i)
                    
            for(j=0; j<n; ++j)
                        
            if(!visited[i][j] && grid[i][j]=='@') {
                            
            ++count;
                            dfs_inner(i, j);
                        }
            }

            int
            main(
            int argc, char **argv)
            {
                
            int i;
                
            while(scanf("%d %d"&m, &n)!= EOF && m) {
                    count 
            = 0;
                    memset(visited, 
            0sizeof(visited));
                    
            for(i=0; i<m; ++i)
                        scanf(
            "%s", grid[i]);
                    dfs();
                    printf(
            "%d\n", count);
                }
            }

            Oil Deposits
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 7595Accepted: 4267

            Description

            The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

            Input

            The input contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket. 

            Output

            are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

            Sample Input

            1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5  ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0

            Sample Output

            0 1 2 2 

            Source


            posted on 2011-08-14 10:29 simplyzhao 閱讀(327) 評論(0)  編輯 收藏 引用 所屬分類: R_找工復習2011

            導航

            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久亚洲av综合波多野结衣| 久久久精品一区二区三区| 午夜精品久久久久久久无码| 亚洲国产精品综合久久网络 | 亚洲综合伊人久久综合| 亚洲人成伊人成综合网久久久| 久久这里只有精品久久| 一本综合久久国产二区| 俺来也俺去啦久久综合网| 亚洲欧美国产精品专区久久| 久久久久久午夜成人影院| 久久久精品人妻无码专区不卡| 久久精品国产2020| 精品国产婷婷久久久| 久久久久青草线蕉综合超碰 | 久久精品中文字幕有码| 久久精品中文无码资源站| 青青草原综合久久| 看久久久久久a级毛片| 亚洲精品久久久www| 四虎国产精品免费久久5151| 亚洲午夜久久久久妓女影院| 久久996热精品xxxx| 一级做a爰片久久毛片人呢| 久久久精品国产sm调教网站 | 中文字幕一区二区三区久久网站| 新狼窝色AV性久久久久久| 久久久久亚洲爆乳少妇无 | 乱亲女H秽乱长久久久| 婷婷久久精品国产| 久久久久国产| 人妻无码久久精品| 日韩久久无码免费毛片软件| 九九久久精品国产| 久久久无码精品午夜| 久久久99精品一区二区| 久久人人爽人爽人人爽av| 久久亚洲中文字幕精品一区四| 国产女人aaa级久久久级| 久久综合给合综合久久| 亚洲精品tv久久久久|