Đề bài
Box blur làm mềm bức ảnh bằng cách thay mỗi pixel bằng trung bình của chính nó và các pixel lân cận. Ở đây bức ảnh là một lưới giá trị độ sáng từ 0 đến 255. Với mỗi pixel, xét khối 3 × 3 có tâm là pixel đó và tính trung bình những pixel của khối nằm trong ảnh: 9 pixel nếu ở giữa, 6 pixel nếu ở cạnh, 4 pixel nếu ở góc (còn ít hơn nữa nếu ảnh chỉ rộng 1 hàng hoặc 1 cột). Luôn tính trung bình trên giá trị gốc, không bao giờ dùng những giá trị đã làm mờ.
Làm tròn trung bình đến số nguyên gần nhất, trường hợp đúng nửa thì làm tròn lên. Nếu chỉ dùng số nguyên, với khối có tổng s và số pixel c, kết quả là (2 × s + c) / (2 × c) với phép chia lấy phần nguyên.
Hãy viết box_blur(pixels).
Đầu vào
pixels: Bức ảnh, mỗi hàng là một danh sách. Các hàng có cùng độ dài.
Đầu ra
Trả về ảnh đã làm mờ dưới dạng lưới có cùng kích thước. Ảnh rỗng thì trả về lưới rỗng.
Ràng buộc
0 ≤ số hàng ≤ 50, 1 ≤ số pixel mỗi hàng ≤ 50 khi có ít nhất một hàng
0 ≤ mỗi pixel ≤ 255
Ví dụ
Đầu vào:
pixels = [
[10, 20, 30],
[40, 50, 60],
[70, 80, 90]
]
Kết quả mong đợi:
expected = [
[30, 35, 40],
[45, 50, 55],
[60, 65, 70]
]
Đầu vào:
std::vector<std::vector<long long>> pixels = {
{10, 20, 30},
{40, 50, 60},
{70, 80, 90}
};
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{30, 35, 40},
{45, 50, 55},
{60, 65, 70}
};
Đầu vào:
long[][] pixels = new long[][] {
new long[] {10, 20, 30},
new long[] {40, 50, 60},
new long[] {70, 80, 90}
};
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {30, 35, 40},
new long[] {45, 50, 55},
new long[] {60, 65, 70}
};
Giải thích
Pixel ở góc (giá trị 10) lấy trung bình 10, 20, 40, 50 được 30. Pixel chính giữa lấy trung bình cả chín giá trị được 50. Pixel giữa hàng trên cùng lấy trung bình 10, 20, 30, 40, 50, 60 được 35.
Đầu vào:
pixels = [
[0, 255]
]
Kết quả mong đợi:
expected = [
[128, 128]
]
Đầu vào:
std::vector<std::vector<long long>> pixels = {
{0, 255}
};
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{128, 128}
};
Đầu vào:
long[][] pixels = new long[][] {
new long[] {0, 255}
};
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {128, 128}
};
Giải thích
Khối của mỗi pixel chứa cả hai pixel, và (0 + 255) / 2 = 127.5 làm tròn lên thành 128, nên kết quả là [[128, 128]].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Lặp độ lệch hàng và độ lệch cột từ −1 đến 1 quanh mỗi pixel.
Gợi ý 2
Đếm xem có bao nhiêu pixel lân cận nằm trong lưới, vì ở cạnh và ở góc sẽ ít hơn.
Gợi ý 3
Đọc từ lưới gốc và ghi vào một lưới kết quả riêng.
Độ phức tạp mong đợi
thời gian O(rows × columns), bộ nhớ phụ O(rows × columns)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.