Trong bài toán này, chúng ta được đưa ra một ma trận vuông [] [] có kích thước m X n với mỗi phần tử là 0 hoặc 1. Nếu một phần tử có giá trị 1, điều này có nghĩa là nó được kết nối, nếu giá trị là 0, điều này có nghĩa là không được kết nối. Nhiệm vụ của chúng ta là tìm độ dài đường dẫn tối đa trong ma trận nhị phân.
Mô tả sự cố - Để giải bài toán ta cần tìm đường đi có độ dài lớn nhất trên ma trận, nghĩa là có tất cả 1 phần tử trong ma trận. Trước khi tìm đường dẫn, chúng tôi sẽ chuyển đổi nhiều nhất một 0 thành 1.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
mat[][] = {{1, 0},
{0, 1}} Đầu ra
3
Giải thích
We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.
Cách tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm độ dài sau khi chuyển đổi từng 0 thành 1. Trước tiên, chúng tôi sẽ sử dụng tìm kiếm chiều sâu để tìm độ dài của đường dẫn và sau đó trả về giá trị tối đa của tất cả độ dài đường dẫn.
Một giải pháp hiệu quả sẽ là loại bỏ sự cần thiết phải thực hiện nhiều chuyển đổi và giải quyết một chuyển đổi mang lại giải pháp hứa hẹn nhất. Chúng tôi sẽ tìm một nhóm sao cho việc chuyển từ 0 thành 1 sẽ trả về đường dẫn có độ dài lớn nhất.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
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))) Đầu ra
The length of largest path is 3