• <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 閱讀(326) 評論(0)  編輯 收藏 引用 所屬分類: R_找工復習2011

            導航

            <2011年9月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            伊人久久一区二区三区无码| 久久夜色精品国产噜噜亚洲AV| 777久久精品一区二区三区无码| 2021久久精品国产99国产精品| 精品久久久久久中文字幕| 91精品国产色综合久久| 大美女久久久久久j久久| 一本一道久久a久久精品综合| 婷婷久久香蕉五月综合加勒比| 久久福利青草精品资源站免费| 伊人久久五月天| 久久精品视频网| 久久久久亚洲AV成人网人人网站 | 日产精品99久久久久久| 亚洲国产天堂久久综合网站 | 国产∨亚洲V天堂无码久久久| 国产成人精品久久| 亚洲精品无码成人片久久| 精品无码人妻久久久久久| 色婷婷综合久久久久中文| 久久久久亚洲AV成人网| 久久精品aⅴ无码中文字字幕不卡 久久精品aⅴ无码中文字字幕重口 | 69久久精品无码一区二区| 久久久久久综合网天天| 久久夜色撩人精品国产小说| 国产麻豆精品久久一二三| 97久久国产露脸精品国产| 久久人人爽人爽人人爽av | 少妇高潮惨叫久久久久久| 亚洲国产成人久久精品99| 久久av高潮av无码av喷吹| 99久久成人国产精品免费| 久久精品国产清高在天天线| 亚洲精品无码成人片久久| 久久亚洲精品人成综合网| 伊人久久精品无码av一区| 国产精品久久婷婷六月丁香| 久久精品成人免费观看97| 久久久久国产精品嫩草影院| 久久久国产精品| 中文字幕无码久久精品青草|