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

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久成人精品视频| 狠狠综合久久综合88亚洲| 久久亚洲精品中文字幕三区| 久久精品国产精品亜洲毛片| 欧美午夜A∨大片久久 | 伊人久久国产免费观看视频| 久久精品国产免费观看| 激情五月综合综合久久69| 麻豆亚洲AV永久无码精品久久| 九九久久精品国产| 久久99国产精品一区二区| 久久亚洲精品无码aⅴ大香| 国产成人AV综合久久| www久久久天天com| 亚洲国产美女精品久久久久∴| 久久se这里只有精品| 久久亚洲高清观看| 久久精品国内一区二区三区| 亚洲人成精品久久久久| 亚洲午夜福利精品久久| 久久夜色撩人精品国产| 99精品久久久久久久婷婷| 久久影院综合精品| 亚洲国产另类久久久精品小说| 2021国产精品久久精品| 亚洲伊人久久成综合人影院| 日韩十八禁一区二区久久| 精品国产综合区久久久久久| 伊人久久大香线蕉精品| 精品久久久久久国产| 日本精品久久久中文字幕| 91精品国产综合久久四虎久久无码一级 | 伊人久久一区二区三区无码| 久久久久亚洲AV成人网| 久久成人18免费网站| 久久久久国产视频电影| 久久性精品| 性欧美大战久久久久久久久| 久久人人爽爽爽人久久久| 国产精品久久免费| 久久久91人妻无码精品蜜桃HD|