โจทย์
ให้เรียกช่อง k ช่องที่เรียงต่อกันเป็นเส้นตรงว่า "แนว" ซึ่งอาจเรียงจากซ้ายไปขวาตามแถว จากบนลงล่างตามคอลัมน์ หรือตามแนวทแยงทั้งสองทิศ ให้คูณตัวเลขในแต่ละแนวแล้วหาแนวที่ให้ผลคูณมากที่สุด
จงเขียนฟังก์ชัน largest_product_in_grid(grid, k)
อินพุต
grid: ตารางตัวเลขรูปสี่เหลี่ยมผืนผ้า ทุกแถวมีความยาวเท่ากัน
k: ความยาวของแนว
เอาต์พุต
คืนค่าผลคูณที่มากที่สุดจากทุกแนวที่ยาว k ช่อง ถ้าไม่มีแนวยาว k ช่องที่วางลงในตารางได้เลยไม่ว่าทิศทางใด ให้คืนค่า 0
เงื่อนไข
1 ≤ จำนวนแถว, จำนวนคอลัมน์ ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5
ตัวอย่าง
อินพุต:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 2
ผลลัพธ์ที่คาดหวัง:
expected = 72
อินพุต:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 2;
ผลลัพธ์ที่คาดหวัง:
long long expected = 72;
อินพุต:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 2;
ผลลัพธ์ที่คาดหวัง:
long expected = 72;
คำอธิบาย
แนวที่ดีที่สุดคือ 8 และ 9 ในแถวล่างสุด ได้ 8 × 9 = 72 ส่วนแนวทแยง 5, 9 ได้เพียง 45
อินพุต:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 3
ผลลัพธ์ที่คาดหวัง:
expected = 504
อินพุต:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 3;
ผลลัพธ์ที่คาดหวัง:
long long expected = 504;
อินพุต:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 3;
ผลลัพธ์ที่คาดหวัง:
long expected = 504;
คำอธิบาย
แถวล่างสุดให้ 7 × 8 × 9 = 504 ซึ่งมากกว่าคอลัมน์ขวาสุด 3 × 6 × 9 = 162 และมากกว่าแนวทแยงทุกแนว
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ใช้แค่สี่ทิศทางก็พอ ได้แก่ ขวา ลง ทแยงลงขวา และทแยงลงซ้าย ทิศอื่นเป็นแนวเดิมที่อ่านย้อนกลับ
คำใบ้ 2
จากช่องเริ่มต้นแต่ละช่อง ให้ตรวจว่าช่องสุดท้ายของแนวยังอยู่ในตาราง
คำใบ้ 3
คืนค่า 0 เฉพาะเมื่อไม่มีแนวยาว k ช่องที่วางในตารางได้เลย
ความซับซ้อนที่คาดหวัง
เวลา O(rows × cols × k), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน