Найдите самое длинное целое число, когда оно соединено внутри сетки - PullRequest
Новая
       67

Найдите самое длинное целое число, когда оно соединено внутри сетки

0 голосов
/ 08 марта 2020

Для данной матрицы самое длинное целое число длины 4 равно 9121 

A = [
[9, 1, 1, 0, 7],
[1, 0, 2, 1, 0],
[1, 9, 1, 1, 0],
]
rows = 3
cols = 5

Это мой код Python Для данной строки и столбца (i, j) Я пытаюсь найти все пути длины четыре 

def find_the_path(A, rows, cols, i, j):
    stack = []
    count = 0
    result = []
    seen = set()
    stack.append((i, j))
    while stack:
        if length(result) == 4:
            result = result[1:]
            seen.clear()

        x, y = stack.pop()
        result.append(A[x][y])
        seen.add(A[x][y])
        count += 1
        # Checking right, left, down, up
        # Trying to use stack, so that I can pop the last element
        # Storing the result in a list and checking for length 4
        for d in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            next_x, next_y = x + d[0], y + d[1]
            if 0 <= next_x < rows and 0 <= next_y < cols:
                if A[next_x][next_y] not in seen and length(result) < 4:
                    stack.append((next_x, next_y))
                    # result.append(A[next_x][next_y])
                    seen.add(A[next_x][next_y])
                    count += 1
                if length(result) == 4:
                    print(result)
                    break

Я не уверен, почему это не печать элементов из [0,1]

Приведенный выше код печатает 

9,1,1,9
1,1,9,0
1,9,0,1

Я потратил много мое время без Googling это и не в состоянии закончить sh это. Мне не нужен код, мне нужен подход для решения этой проблемы.

1 Ответ

0 голосов
/ 08 марта 2020

одна строка дзен python (введите import this в терминале python) равна

Простое лучше, чем сложное.

Ваш пытаясь сделать глубину сначала поиск. Поиск в глубину - это рекурсивный алгоритм. Как правило, вы можете реализовать рекурсивный алгоритм двумя способами: процедурным и рекурсивным.

процедурный путь, на мой взгляд, более сложен, но часто имеет лучшую производительность и менее ограничен памятью, чем рекурсивный способ.

рекурсивный способ в python по моему опыту проще читать и писать. но он более ограничен памятью процедурным способом.

потому что, глядя на небольшую глубину из 4 шагов, я думаю, что проще использовать рекурсивный подход.

Ваша реализация иногда использует точки ((x, y)), а иногда значения (1). Ваша реализация будет проще, если вы будете использовать точки для построения пути, а затем создадите новый путь, в котором будут храниться значения вместо точек, когда вы будете готовы к возвращению.

создание соседних точек (next_x, next_y) в вашем алгоритме. я бы поставил эту часть в отдельную функцию. 

def neigbours(x, y, rows, cols):
    for rel_x, rel_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        next_x, next_y = x + rel_x, y + rel_y
        if 0 <= next_x < rows and 0 <= next_y < cols:
            yield next_x, next_y

# so that you can do the following
rows, cols = 3, 5
x, y = 0, 0
for next_x, next_y in neigbours(x, y, rows, cols):
    print(next_x, next_y)

# output
0 1
1 0
...