โจทย์
Box blur ทำให้ภาพนุ่มนวลขึ้นโดยแทนทุกพิกเซลด้วยค่าเฉลี่ยของตัวมันเองกับพิกเซลข้างเคียง ในโจทย์นี้ภาพเป็นตารางของค่าความสว่าง 0 ถึง 255 สำหรับแต่ละพิกเซล ให้ดูบล็อกขนาด 3 x 3 ที่มีพิกเซลนั้นอยู่ตรงกลาง แล้วหาค่าเฉลี่ยของพิกเซลในบล็อกที่อยู่ภายในภาพ คือ 9 พิกเซลสำหรับตรงกลางภาพ 6 พิกเซลตามขอบ และ 4 พิกเซลที่มุม (น้อยกว่านี้สำหรับภาพที่กว้างหรือสูงเพียง 1 แถวหรือ 1 คอลัมน์) ต้องหาค่าเฉลี่ยจากค่าเดิมเสมอ ห้ามใช้ค่าที่เบลอไปแล้ว
ให้ปัดค่าเฉลี่ยเป็นจำนวนเต็มที่ใกล้ที่สุด โดยถ้าเป็นครึ่งพอดีให้ปัดขึ้น ถ้าใช้แต่จำนวนเต็ม สำหรับบล็อกที่มีผลรวม s และจำนวนพิกเซล c จะได้ (2 × s + c) / (2 × c) โดยใช้การหารแบบปัดเศษทิ้ง
จงเขียน box_blur(pixels)
อินพุต
pixels: ภาพ แถวละหนึ่งลิสต์ ทุกแถวยาวเท่ากัน
เอาต์พุต
คืนค่าภาพที่เบลอแล้วเป็นตารางขนาดเท่าเดิม ถ้าภาพว่าง ให้คืนค่าตารางว่าง
เงื่อนไข
0 ≤ จำนวนแถว ≤ 50 และ 1 ≤ จำนวนพิกเซลต่อแถว ≤ 50 เมื่อมีอย่างน้อยหนึ่งแถว
0 ≤ แต่ละพิกเซล ≤ 255
ตัวอย่าง
อินพุต:
pixels = [
[10, 20, 30],
[40, 50, 60],
[70, 80, 90]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[30, 35, 40],
[45, 50, 55],
[60, 65, 70]
]
อินพุต:
std::vector<std::vector<long long>> pixels = {
{10, 20, 30},
{40, 50, 60},
{70, 80, 90}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{30, 35, 40},
{45, 50, 55},
{60, 65, 70}
};
อินพุต:
long[][] pixels = new long[][] {
new long[] {10, 20, 30},
new long[] {40, 50, 60},
new long[] {70, 80, 90}
};
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {30, 35, 40},
new long[] {45, 50, 55},
new long[] {60, 65, 70}
};
คำอธิบาย
มุมที่เป็น 10 ได้ค่าเฉลี่ยของ 10, 20, 40, 50 เท่ากับ 30 ตรงกลางได้ค่าเฉลี่ยของทั้งเก้าค่าเท่ากับ 50 ส่วนตรงกลางแถวบนได้ค่าเฉลี่ยของ 10, 20, 30, 40, 50, 60 เท่ากับ 35
อินพุต:
pixels = [
[0, 255]
]
ผลลัพธ์ที่คาดหวัง:
expected = [
[128, 128]
]
อินพุต:
std::vector<std::vector<long long>> pixels = {
{0, 255}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::vector<long long>> expected = {
{128, 128}
};
อินพุต:
long[][] pixels = new long[][] {
new long[] {0, 255}
};
ผลลัพธ์ที่คาดหวัง:
long[][] expected = new long[][] {
new long[] {128, 128}
};
คำอธิบาย
บล็อกของแต่ละพิกเซลมีพิกเซลทั้งสองตัว และ (0 + 255) / 2 = 127.5 ปัดขึ้นเป็น 128 จึงได้ [[128, 128]]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
วนลูปค่าเลื่อนของแถวและคอลัมน์ตั้งแต่ −1 ถึง 1 รอบแต่ละพิกเซล
คำใบ้ 2
นับว่ามีพิกเซลข้างเคียงกี่ตัวที่อยู่ในตาราง เพราะขอบและมุมมีน้อยกว่า
คำใบ้ 3
อ่านค่าจากตารางต้นฉบับ แล้วเขียนลงตารางผลลัพธ์อีกตารางหนึ่ง
ความซับซ้อนที่คาดหวัง
เวลา O(rows × columns), หน่วยความจำเพิ่ม O(rows × columns)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน