숫자 그리드가 있다고 가정합니다. 우리는 뱀 시퀀스를 찾아 반환해야 합니다. 여러 스네이크 시퀀스가 있는 경우 하나만 반환합니다. 우리가 알고 있듯이 스네이크 시퀀스는 그리드의 인접한 숫자를 사용하여 만들어지므로 각 숫자에 대해 오른쪽의 숫자 또는 그 아래의 숫자는 해당 값의 +1 또는 -1입니다. 따라서 현재 값이 그리드 셀(a, b)에 있는 경우 해당 숫자가 ± 1이면 오른쪽(a, b+1)으로 이동하거나 해당 숫자가 ± 1이면 아래로(a+1, b) 이동할 수 있습니다.
따라서 입력이 다음과 같으면
| 10 | 7 | 6 | 3 |
| 9 | 8 | 7 | 6 |
| 8 | 4 | 2 | 7 |
| 2 | 2 | 2 | 8 |
그러면 출력은 6, 시퀀스 − 10(0, 0) ~ 9(1, 0) ~ 8(1, 1) ~ 7(1, 2) ~ 6(1, 3) ~ 7(2, 3)이 됩니다. ~ 8(3, 3)
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
get_path() 함수를 정의합니다. 그리드, 매트, i, j
가 필요합니다. -
경로 :=새 목록
-
pt :=점 [i, j]
-
경로 끝에 pt 삽입
-
grid[i, j]가 0이 아닌 동안 수행
-
i> 0이고 grid[i, j]-1이 grid[i-1, j]와 같으면
-
pt :=[i-1, j]
-
경로 끝에 pt 삽입
-
나는 :=나는 - 1
-
-
그렇지 않으면 j> 0이고 grid[i, j]-1이 grid[i, j-1]과 같으면
-
pt :=[i, j-1]
-
경로 끝에 pt 삽입
-
j :=j - 1
-
-
-
반환 경로
-
기본 방법에서 다음을 수행하십시오 -
-
lookup :=M x N 크기의 격자를 만들고 0으로 채움
-
length_max :=0, max_row :=0, max_col :=0
-
범위 0에서 M에 있는 i에 대해 수행
-
0에서 N 사이의 j에 대해 수행
-
i 또는 j가 0이 아니면
-
if (i> 0 an 및 |grid[i-1, j] - grid[i, j]|가 1이면
-
lookup[i,j] =최대 lookup[i,j],lookup[i-1,j] + 1)
-
length_max
-
length_max :=조회[i, j]
-
max_row :=i
-
max_col :=j
-
-
-
if (j> 0 및 |grid[i, j-1] - grid[i, j]|가 1이면
-
length_max
-
lookup[i,j] =최대 lookup[i,j],lookup[i,j-1] + 1)
-
length_max :=조회[i, j]
-
max_row :=i
-
max_col :=j
-
-
-
-
-
-
표시 length_max
-
경로 :=get_path(조회, 그리드, max_row, max_col)
-
경로의 모든 요소를 역순으로 인쇄
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. &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) 입력
[[10, 7, 6, 3], [9, 8, 7, 6], [8, 4, 2, 7], [2, 2, 2, 8]]
출력
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]