Giả sử chúng ta có một lưới các số; chúng ta phải tìm một chuỗi con rắn và trả lại nó. Nếu có nhiều chuỗi con rắn, thì chỉ trả về một con. Như chúng ta biết, một dãy con rắn được tạo ra bằng cách sử dụng các số liền kề trong lưới, vì vậy đối với mỗi số, số ở bên phải hoặc số bên dưới nó là +1 hoặc -1 giá trị của nó. Vì vậy, nếu giá trị hiện tại nằm trong ô lưới (a, b), chúng ta có thể di chuyển sang phải (a, b + 1) nếu số đó là ± 1 hoặc di chuyển xuống dưới (a + 1, b) nếu số đó là ± 1.
Vì vậy, nếu đầu vào giống như
| 10 | 7 | 6 | 3 |
| 9 | 8 | 7 | 6 |
| 8 | 4 | 2 | 7 |
| 2 | 2 | 2 | 8 |
thì đầu ra sẽ là 6, dãy - 10 (0, 0) đến 9 (1, 0) đến 8 (1, 1) đến 7 (1, 2) đến 6 (1, 3) đến 7 (2, 3) đến 8 (3, 3)
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm get_path (). Điều này sẽ lấy lưới, mat, i, j
-
path:=a new list
-
pt:=a point [i, j]
-
chèn pt vào cuối đường dẫn
-
trong khi lưới [i, j] không phải là 0, do
-
nếu i> 0 và lưới [i, j] -1 giống với lưới [i-1, j] thì
-
pt:=[i-1, j]
-
chèn pt vào cuối đường dẫn
-
i:=i - 1
-
-
ngược lại khi j> 0 và lưới [i, j] -1 giống với lưới [i, j-1] thì
-
pt:=[i, j-1]
-
chèn pt vào cuối đường dẫn
-
j:=j - 1
-
-
-
đường dẫn trở lại
-
Từ phương thức chính, thực hiện như sau -
-
lookup:=tạo một lưới kích thước M x N và điền bằng 0
-
length_max:=0, max_row:=0, max_col:=0
-
đối với tôi trong phạm vi từ 0 đến M, hãy thực hiện
-
đối với j trong phạm vi từ 0 đến N, thực hiện
-
nếu tôi hoặc j khác 0, thì
-
if (i> 0 an and | grid [i-1, j] - grid [i, j] | is 1, then
-
tra cứu [i, j] =tối đa tra cứu [i, j], tra cứu [i-1, j] + 1)
-
nếu length_max
-
length_max:=lookup [i, j]
-
max_row:=i
-
max_col:=j
-
-
-
if (j> 0 and | grid [i, j-1] - grid [i, j] | is 1, then
-
nếu length_max
-
tra cứu [i, j] =tối đa tra cứu [i, j], tra cứu [i, j-1] + 1)
-
length_max:=lookup [i, j]
-
max_row:=i
-
max_col:=j
-
-
-
-
-
-
hiển thị length_max
-
path:=get_path (tra cứu, lưới, max_row, max_col)
-
in tất cả các phần tử trong đường dẫn theo thứ tự ngược lại
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn &mius;
M = 4
N = 4
def get_path(grid, mat, i, j):
path = list()
pt = [i, j]
path.append(pt)
while (grid[i][j] != 0):
if (i > 0 and grid[i][j]-1 == grid[i-1][j]):
pt = [i-1, j]
path.append(pt)
i -= 1
elif (j > 0 and grid[i][j]-1 == grid[i][j-1]):
pt = [i, j-1]
path.append(pt)
j -= 1
return path
def get_sequence(grid):
lookup = [[0 for i in range(N)] for j in range(M)]
length_max = 0
max_row = 0
max_col = 0
for i in range(M):
for j in range(N):
if (i or j):
if (i > 0 and
abs(grid[i-1][j] - grid[i][j]) == 1):
lookup[i][j] = max(lookup[i][j],lookup[i-1][j] + 1)
if (length_max < lookup[i][j]):
length_max = lookup[i][j]
max_row = i
max_col = j
if (j > 0 and
abs(grid[i][j-1] - grid[i][j]) == 1):
lookup[i][j] = max(lookup[i][j],lookup[i][j-1] + 1)
if (length_max < lookup[i][j]):
length_max = lookup[i][j]
max_row = i
max_col = j
print("Maximum length:", length_max)
path = get_path(lookup, grid, max_row, max_col)
print("Sequence is:")
for ele in reversed(path):
print(grid[ele[0]][ele[1]], " [", ele[0], ", ", ele[1], "]", sep = "")
grid = [
[10, 7, 6, 3],
[9, 8, 7, 6],
[8, 4, 2, 7],
[2, 2, 2, 8]]
get_sequence(grid) Đầu vào
[[10, 7, 6, 3], [9, 8, 7, 6], [8, 4, 2, 7], [2, 2, 2, 8]]
Đầu ra
Maximum length: 6 Sequence is: 10 [0, 0] 9 [1, 0] 8 [1, 1] 7 [1, 2] 6 [1, 3] 7 [2, 3] 8 [3, 3]