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

            導航

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品免费一区二区| 潮喷大喷水系列无码久久精品| 99久久夜色精品国产网站| 97精品久久天干天天天按摩| 国产精品激情综合久久 | 日韩精品久久无码人妻中文字幕| 久久久久久国产精品免费无码| 久久最近最新中文字幕大全| 一本久久综合亚洲鲁鲁五月天| 久久香蕉超碰97国产精品| 国产成人无码精品久久久免费| 国产成人久久精品一区二区三区| 九九99精品久久久久久| 奇米影视7777久久精品人人爽| 九九久久99综合一区二区| 亚洲AV无码久久精品蜜桃| 国产一区二区三精品久久久无广告 | 7777久久久国产精品消防器材| 国产精品久久久久久久午夜片 | 亚洲国产精品狼友中文久久久| 精品免费久久久久久久| 久久久久久久久久久久久久| 久久久久亚洲爆乳少妇无 | 99精品久久久久中文字幕| 久久久久久国产a免费观看黄色大片| 色综合久久综精品| 一本一道久久精品综合| 国产精品久久久久AV福利动漫| 亚洲国产精品一区二区久久hs| 久久久久久免费视频| 久久久久久精品成人免费图片| 99精品国产免费久久久久久下载| 性欧美大战久久久久久久| 亚洲国产成人精品无码久久久久久综合 | 久久精品国产精品亜洲毛片| 亚洲国产精品久久久久久| 91久久精品国产91性色也| 国产成人99久久亚洲综合精品| 激情五月综合综合久久69| 久久久久国产精品麻豆AR影院| 久久久久国产|