11545: 【原1545】RGB Cover

题目

题目描述

author: BreakVoid, Zhijian Liu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1545

Description

有一块\(n*m\)的白色的棋盘，现在对它进行一些操作，每次将对以一个\((x,y)\)为圆心，\(r\)为半径的圆所覆盖(\((x',y')\)被覆盖当且仅当\((x'-x)^2+(y'-y)^2\leq r^2\))的格子染成Red, Blue, Green三种颜色中的一种，注意后进行的染色可以覆盖之前的染色。

求进行k次染色后，棋盘上Red, Blue, Green颜色的格子有多少个？

Input Format

共\(k + 1\)行，第一行包含三个整数\(n,m,k\)。

后\(k\)行每行包含\(3\)个整数\(x,y,r\)和一个操作R,G,B，表示把以一个\((x,y)\)为圆心，\(r\)为半径的圆所完全覆盖的格子染成Red,Blue,Green三种颜色中的一种。

Output Format

输出包含三行，按照Red, Green, Blue的顺序输出各种颜色的格子数量，每行的格式分别为Red:, Green:, Blue:。

Sample Input 1

3 3 3
1 1 2 R
3 3 2 B
1 3 1 G

Sample Output 1

Red:2
Green:3
Blue:4

Sample Input 2

4 5 4
1 2 3 B
4 1 0 G
3 5 2 R
1 3 0 B

Sample Output 2

Red:8
Green:1
Blue:10

Limits

对于100%的数据，\(n,m\leq 1000,k\leq 10^4\)

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

int n, m, k;
bool visited[1009][1009] = { 0 };
int ops[10009][4] = { 0 };

int cx, cy, r;

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

bool check_av(int x, int y) {
    return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < k; ++i) {
        cin >> cx >> cy >> r;
        --cx;
        --cy;
        ops[i][0] = cx;
        ops[i][1] = cy;
        ops[i][2] = r;
        char temp[10];
        cin >> temp;
        if (temp[0] == 'R') {
            ops[i][3] = 1;
        }
        else if (temp[0] == 'G') {
            ops[i][3] = 2;
        }
        else {
            ops[i][3] = 3;
        }
    }

    int cnt[4] = { 0 };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int color = 0;
            for (int a = k - 1; a >= 0; --a) {
                cx = ops[a][0], cy = ops[a][1], r = ops[a][2];
                if (check_av(i, j)) {
                    color = ops[a][3];
                    break;
                }
            }
            ++cnt[color];
        }
    }

    cout << "Red:" << cnt[1] << endl << "Green:" << cnt[2] << endl << "Blue:" << cnt[3];

    return 0;
}