สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยที่เมทริกซ์ [r, c] แทนจำนวนเหรียญในเซลล์นั้น เราสามารถเริ่มต้นจากตำแหน่งใดก็ได้และต้องการเก็บเหรียญโดยการย้ายทิศทางใด ๆ จากสี่ทิศทาง (ขึ้น ลง ซ้ายและขวา ไม่ใช่แนวทแยง) เมื่อเราย้ายไปที่เซลล์ เหรียญจะถูกรวบรวมและมูลค่าของเซลล์นั้นจะกลายเป็น 0 เราไม่สามารถไปที่เซลล์ที่มี 0 เหรียญได้ เราต้องค้นหาจำนวนเหรียญสูงสุดที่เรารวบรวมได้
ดังนั้นหากอินพุตเป็นแบบ
| 2 | 4 | 3 |
| 3 | 6 | 0 |
| 2 | 0 | 12 |
จากนั้นผลลัพธ์จะเป็น 18 เนื่องจากเราสามารถใช้เส้นทาง 2 −> 3 −> 6 −> 4 −> 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
หากเมทริกซ์ว่างเปล่า
-
คืนค่า 0
-
-
n :=จำนวนแถวของเมทริกซ์ m :=จำนวนคอลัมน์ของเสื่อ
-
x :=รายการที่ชอบ [-1, 1, 0, 0], y :=รายการที่ชอบ [0, 0, -1, 1]
-
กำหนดฟังก์ชัน util() นี่จะใช้เวลา a, b
-
ยกเลิก :=0
-
สำหรับ k ในช่วง 0 ถึง 3 ทำ
-
(t1, t2) :=(x[k] + a, y[k] + b)
-
ถ้า (t1, t2) เป็นเซลล์ที่ถูกต้อง
-
t :=mat[t1, t2], mat[t1, t2] :=0
-
ret :=สูงสุดของ ret และ (util(t1, t2) + t)
-
mat[t1, t2] :=t
-
-
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
res :=0
-
สำหรับฉันในช่วง 0 ถึง n − 1 ทำ
-
สำหรับ j ในช่วง 0 ถึง m − 1 ทำ
-
ถ้า mat[i, j] ไม่ใช่ศูนย์ ดังนั้น
-
t :=mat[i, j], mat[i, j] :=0
-
res :=สูงสุดของ res และ (util(i, j) + temp)
-
-
-
-
ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, mat): if not mat: return 0 n, m = len(mat), len(mat[0]) x, y = [−1, 1, 0, 0], [0, 0, −1, 1] def ok(a, b): return 0 <= a < n and 0 <= b < m and mat[a][b] def util(a, b): ret = 0 for k in range(4): t1, t2 = x[k] + a, y[k] + b if ok(t1, t2): t, mat[t1][t2] = mat[t1][t2], 0 ret = max(ret, util(t1, t2) + t) mat[t1][t2] = t return ret res = 0 for i in range(n): for j in range(m): if mat[i][j]: temp, mat[i][j] = mat[i][j], 0 res = max(res, util(i, j) + temp) return res ob = Solution() matrix = [ [2, 4, 3], [3, 6, 0], [2, 0, 12] ] print(ob.solve(matrix))
อินพุต
[ [2, 4, 3], [3, 6, 0], [2, 0, 12] ]
ผลลัพธ์
18
