• Oil Deposits


    原题链接

    题解

    题目是说有多少个连通块,每一次以一个开始,遍历并标记他能够到达的点(就是同一个连通块中的点)

    代码如下

    dfs

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <stack>
    #include <map>
    #include <queue>
    #include <sstream>
    #include <set>
    #include <cctype>
    #define mem(a,b) memset(a,b,sizeof(a))
    
    using namespace std;
    
    typedef pair<int, int> PII;
    const int N = 101;
    int m, n;
    char g[N][N];
    int dx[8] = {0,0,1,1,1,-1,-1,-1}, dy[8] = {1,-1,0,1,-1,0,1,-1};
    
    void dfs(int a, int b){
        for(int i = 0; i < 8; ++i){
            int x = a + dx[i], y = b + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n && g[x][y] == '@'){
                g[x][y] = '*';
                dfs(x, y);
            }
        }
    }
    
    int main(){
    
        while(cin >> m >> n){
            if(m == 0) break;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j)
                cin >> g[i][j];
            }
    
            int res = 0;
    
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(g[i][j] == '*') continue;
                    res++;
                    dfs(i, j);
                }
            }
            cout << res << endl;
        } 
    
        return 0;
    }
    

    bfs

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <stack>
    #include <map>
    #include <queue>
    #include <sstream>
    #include <set>
    #include <cctype>
    #define mem(a,b) memset(a,b,sizeof(a))
    
    using namespace std;
    
    typedef pair<int, int> PII;
    const int N = 101;
    char g[N][N];
    int dx[8] = {0,0,1,1,1,-1,-1,-1}, dy[8] = {1,-1,0,1,-1,0,1,-1};
    
    int main(){
        int m, n;
        while(cin >> m >> n){
            if(m == 0) break;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j)
                cin >> g[i][j];
            }
    
            int res = 0;
    
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(g[i][j] == '*') continue;
                    queue<PII> q; res ++;
                    q.push({i, j}); g[i][j] = '*';
                    
                    while(q.size()){
                        auto t = q.front(); q.pop();
                        for(int k = 0; k < 8; ++k){
                            int x = t.first + dx[k], y = t.second + dy[k];
                            if(x >= 0 && x < m && y >= 0 && y < n && g[x][y] == '@'){
                                q.push({x, y}); g[x][y] = '*';
                            }
                        }
                    }
    
                }
            }
            cout << res << endl;
        } 
    
        return 0;
    }
    

    这个题目还可以用并查集做,以后水平提高了补上

  • 相关阅读:
    c++ 虚继承与继承的差异 (转)
    主题:PageRank解释
    (转)开源爬虫larbin分析
    Django随笔
    原生爬虫小Demo
    SVN
    Python的正则表达式与JSON
    类库 方法 模块等
    笔记
    自动补全Typeahead
  • 原文地址:https://www.cnblogs.com/Lngstart/p/13235072.html
一二三 - 开发者的网上家园