ในปัญหานี้ เราได้รับแผ่นเมทริกซ์สี่เหลี่ยมจัตุรัส[][] ขนาด m X n โดยแต่ละองค์ประกอบเป็น 0 หรือ 1 หากองค์ประกอบมีค่า 1 แสดงว่าเชื่อมต่อแล้ว หากค่าเป็น 0 แสดงว่า ไม่ได้เชื่อมต่อ งานของเราคือการหาความยาวเส้นทางสูงสุดในเมทริกซ์ไบนารี
คำอธิบายปัญหา − ในการแก้ปัญหา เราจำเป็นต้องค้นหาเส้นทางความยาวที่ใหญ่ที่สุดบนเมทริกซ์ ซึ่งหมายถึงองค์ประกอบทั้งหมด 1 รายการในเมทริกซ์ ก่อนหาเส้นทาง เราจะแปลงค่า 0 เป็น 1 อย่างมากที่สุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
mat[][] = {{1, 0},
{0, 1}} ผลลัพธ์
3
คำอธิบาย
We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือ การหาความยาวหลังจากแปลงค่า 0 เป็น 1 แต่ละตัว เราจะใช้การค้นหาเชิงลึกก่อนเพื่อค้นหาความยาวของเส้นทาง จากนั้นคืนค่าสูงสุดของความยาวเส้นทางทั้งหมด
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการกำจัดความจำเป็นในการแปลงหลาย ๆ ครั้งและจัดการกับสิ่งที่ให้โซลูชันที่มีแนวโน้มดีที่สุด เราจะพบกลุ่มที่การเปลี่ยน 0 เป็น 1 จะคืนค่าเส้นทางที่ยาวที่สุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
def FindNeighbor(R, C, N):
for nr, nc in (((R - 1), C), ( (R + 1) , C), (R, (C - 1) ), (R, (C + 1) )):
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
def DFSTraversal(R, C, index, mat, N):
maxLen = 1
mat[R][C] = index
for nr, nc in FindNeighbor(R, C, N):
if mat[nr][nc] == 1:
maxLen += DFSTraversal(nr, nc, index)
return maxLen
def findLargestPath(mat):
N = len(mat)
maxPath = {}
index = 2
for i in range(N):
for j in range(N):
if mat[i][j] == 1:
maxPath[index] = DFSTraversal(i, j, index, mat, N)
index += 1
maxPathLen = max(maxPath.values() or [0])
for i in range(N):
for j in range(N):
if mat[i][j] == 0:
seen = {mat[nr][nc] for nr, nc in FindNeighbor(i, j, N) if mat[nr][nc] > 1}
maxPathLen = max(maxPathLen, 1 + sum(maxPath[i] for i in seen))
return maxPathLen
I = [[1, 0], [0, 1]]
print("The length of largest path is " + str(findLargestPath(I))) ผลลัพธ์
The length of largest path is 3
