• Codeforces Round #771 (Div. 2) D. Big Brush


    Codeforces Round #771 (Div. 2) D. Big Brush

    Let’s try to build the solution from the last operation to the first operation. The last operation can be any 2 × 2 2×2 2×2 square painted in a single color. If there is no such square, it is clearly impossible. Otherwise, this square being the last operation implies that we could previously color its cells in any color, multiple times, without any consequences. We will name these special cells.

    What happens when we run out of 2 × 2 2×2 2×2 squares painted in a single color? Well, we can use the special cells described above. The next operation considered can be any 2 × 2 2×2 2×2 square such that all its non-special cells are painted in the same color. If there is no such square, it is clearly impossible.

    We now have a correct solution. It consists of at most n m nm nm operation because at each step we turn at least one non-special cell into a special one and there are n m nm nm cells. We can implement this solution similar to BFS. First, insert all 2 × 2 2×2 2×2 squares painted in a single color into a queue. Then, at each step take the square in the front of the queue, add it to the solution and make all its non-special cells special. When making a cell special, check all 2 × 2 2×2 2×2 squares that contain it and if some of them meet the condition after the current step, insert them into the queue. Note that there are at most 9 9 9 such squares.

    在这里插入图片描述

    Time complexity: O ( n m ) O(nm) O(nm).

    #include
    using namespace std;
    
    typedef pair<int,int> PII;
    const int N = 1010;
    
    int g[N][N];
    bool vis[N][N];
    
    int findcolor(int i,int j)
    {
        if(g[i][j]==0 && g[i+1][j]==0 && g[i+1][j+1]==0 && g[i][j+1]==0)
            return 0;
    
        int color=0;
        for(auto x:{i,i+1})
            for(auto y:{j,j+1})
                if(g[x][y]!=0)
                    color=g[x][y];
    
        for(auto x:{i,i+1})
            for(auto y:{j,j+1})
                if(g[x][y]!=0 && g[x][y]!=color)
                    return -1;
        return color;
    }
    
    signed main()
    {
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[i][j];
    
        queue<PII> Q;
    
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                if(findcolor(i,j)>0)
                {
                    Q.push({i,j});
                    vis[i][j]=true;
                }
    
        vector<array<int,3>> cnt;
        while(!Q.empty())
        {
            PII t=Q.front();Q.pop();
            int color=findcolor(t.first,t.second);
            if(color<=0) continue;
    
            g[t.first][t.second]=g[t.first+1][t.second]=g[t.first][t.second+1]=g[t.first+1][t.second+1]=0;
            cnt.push_back({t.first,t.second,color});
    
            for(auto x:{t.first-1,t.first,t.first+1})
                for(auto y:{t.second-1,t.second,t.second+1})
                {
                    if(x<=0||x>=n||y<=0||y>=m) continue;
                    if(findcolor(x,y)<=0||vis[x][y]) continue;
                    vis[x][y]=true;
                    Q.push({x,y});
                }
        }
    
        bool flag=true;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(g[i][j])
                    flag=false;
    
        if(!flag) cout<<"-1\n";
        else
        {
            cout<<cnt.size()<<endl;
            reverse(cnt.begin(),cnt.end());
            for(auto [a,b,c]:cnt)
                cout<<a<<" "<<b<<" "<<c<<"\n";
        }
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
  • 相关阅读:
    图的遍历 广度优先遍历(爱思创)
    day09扩展:键盘录入笔记
    C# - XMLHelper :一个操作XML的简单类库
    深度学习CNN--眼睛姿态识别联练习
    webpack基础
    油封与O型圈相同吗?
    归并排序知识总结
    TorchServe搭建codeBERT分类模型服务
    如何使IOT2050成为PN设备
    el-table 合集行合并
  • 原文地址:https://blog.csdn.net/qq_52792570/article/details/127663113