Hướng dẫn giải của [Beginner Free Contest 19] COLORING
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Hình chữ nhật W × H (W, H ≤ 100) chứa N điểm (N ≤ 100). Mỗi điểm i có hướng a_i, tô màu toàn bộ phần bên trái, phải, dưới hoặc trên điểm đó. Tính diện tích phần chưa được tô.
Sub 1: Tô từng ô đơn vị — ~O(N · W · H)~
Chia hình chữ nhật thành W · H ô vuông đơn vị, ô (c, r) có toạ độ [c, c+1] × [r, r+1]. Với mỗi điểm và mỗi hướng, đánh dấu các ô nằm hoàn toàn về phía tương ứng (ví dụ a = 1 thì c < x). Cuối cùng đếm số ô chưa được đánh dấu. Mỗi ô là 1 đơn vị diện tích. Độ phức tạp N·W·H ≤ 10^6 nên đủ nhanh.
Kết quả chấm: 20/20 (PASS 20/20)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int W, H, N;
cin >> W >> H >> N;
// Chia hinh chu nhat thanh W*H o don vi; o (c, r) phu doan [c, c+1] x [r, r+1].
vector<vector<int>> tom(W, vector<int>(H, 0)); // 1 neu o da bi to mau
for (int i = 0; i < N; i++) {
int x, y, a;
cin >> x >> y >> a;
for (int c = 0; c < W; c++)
for (int r = 0; r < H; r++) {
bool cung = false;
if (a == 1 && c < x) cung = true; // ben trai: x < xi
if (a == 2 && c >= x) cung = true; // ben phai: x > xi
if (a == 3 && r < y) cung = true; // ben duoi: y < yi
if (a == 4 && r >= y) cung = true; // ben tren: y > yi
if (cung) tom[c][r] = 1;
}
}
long long chua = 0;
for (int c = 0; c < W; c++)
for (int r = 0; r < H; r++)
if (!tom[c][r]) chua++;
cout << chua << "\n";
return 0;
}
Bình luận