题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

void solve() {
    int R,C,n;
    cin >> R >> C;
    vector<vector<int>> v(R,vector<int>(C,0));
    vector<string> g(R);
    for(auto &t:g) cin >> t;
    for(int i = 0; i < R; i ++ ) {
        for(int j = 0; j < C; j ++ ) {
            v[i][j] = g[i][j] - '0';
        }

    }
    cin >> n;

    for(int i = 0; i < n; i ++ ) {
        string op;
        cin >> op;
        if(op == "Q") {
            vector<vector<int>> st(R,vector<int>(C,0));

            auto bfs = [&](int x, int y) -> void {
                queue<PII> q;
                q.push({x,y});
                st[x][y] = true;
                while(q.size()) {
                    auto t = q.front();
                    q.pop();
                    for(int i = 0; i < 4; i ++ ) {
                        int a = t.first + dx[i];
                        int b = t.second + dy[i];
                        if(a >= 0 && a < R && b >= 0 && b < C && !st[a][b] && v[a][b] == 1) {
                            st[a][b] = true;
                            q.push({a,b});
                        }
                    }
                }
            };

            int res = 0;
            for(int i = 0; i < R; i ++ ) {
                for(int j = 0; j < C; j ++ ) {
                    if(v[i][j] == 1 && !st[i][j]) {
                        bfs(i,j);
                        res ++ ;
                    }
                }
            }
            cout << res << endl;
        } else {
            int x,y,z;
            cin >> x >> y >> z;
            v[x][y] = z;
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int i = 1; i <= T; i ++ ) {
        cout << "Case #" << i <<":\n";
        solve();
    }

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla