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

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            色8久久人人97超碰香蕉987| 久久精品国产清自在天天线| 99久久超碰中文字幕伊人| 九九久久自然熟的香蕉图片| 久久精品国产亚洲Aⅴ香蕉| 精品久久久无码中文字幕天天| 久久国产乱子伦免费精品| 中文字幕亚洲综合久久| 久久99国产一区二区三区| 一级做a爱片久久毛片| 国产成人久久精品二区三区| 久久婷婷人人澡人人| 无码伊人66久久大杳蕉网站谷歌| 亚洲中文久久精品无码| 国产精品久久久久久吹潮| 国色天香久久久久久久小说| 久久99热这里只有精品66| 国产午夜福利精品久久| 人妻系列无码专区久久五月天| 久久不射电影网| 天天躁日日躁狠狠久久| 亚洲人成精品久久久久| 99久久er这里只有精品18| 久久国产精品99久久久久久老狼| 久久久久久免费一区二区三区 | 久久精品国产精品亚洲下载| 国产精品久久久久一区二区三区| 中文字幕无码av激情不卡久久| 狠狠色丁香婷婷综合久久来 | 最新久久免费视频| 一本大道加勒比久久综合| 免费久久人人爽人人爽av| 潮喷大喷水系列无码久久精品| 免费精品久久久久久中文字幕| 精品久久久久久久久午夜福利 | 久久久久久久综合日本| 亚洲午夜久久久影院| 色综合久久久久综合99| 久久青草国产精品一区| 久久国产精品77777| 色老头网站久久网|