题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> PII;

int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int main() {
    int n,m,q;
    cin >> m >> n >> q;
    vector<string> g(n,string(m,'.'));

    while(q -- ) {
        int op;
        cin >> op;
        if(op == 0) {
            int x1,y1,x2,y2;
            cin >> y1 >> x1 >> y2 >> x2;
            if(x1 > x2) swap(x1,x2);
            if(y1 > y2) swap(y1,y2);
            if(x1 == x2) {
                for(int i = y1; i <= y2; i ++ ) {
                    if(g[x1][i] == '|' || g[x1][i] == '+') g[x1][i] = '+';
                    else g[x1][i] = '-';
                }
            } else {
                for(int i = x1; i <= x2; i ++ ) {
                    if(g[i][y1] == '-' || g[i][y1] == '+') g[i][y1] = '+';
                    else g[i][y1] = '|';
                }
            }
        } else {
            int x,y;
            char c;
            cin >> y >> x >> c;
            vector<vector<int>> st(n,vector<int>(m,0));
            auto bfs = [&](int bx, int by) -> void {
                queue<PII> q;
                q.push({bx,by});
                st[bx][by] = true;
                g[x][y] = c;
                while(q.size()) {
                    auto t = q.front();
                    q.pop();
                    for(int i = 0; i < 4; i ++ ) {
                        int x = t.first + dx[i];
                        int y = t.second + dy[i];
                        if(x >= 0 && x < n && y >= 0 && y < m && !st[x][y] && (g[x][y]!='-'&&g[x][y]!='+'&&g[x][y]!='|')) {
                            g[x][y] = c;
                            st[x][y] = true;
                            q.push({x,y});
                        }
                    }
                }
            };

            bfs(x,y);
        }
    }
    for(int i = n-1; i >= 0; i -- ) cout << g[i] << endl;

    return 0;
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla