Есть ли выход из лабиринта?

Question

Нужно узнать есть ли выход из лабиринта, вход всегда [0,0], выход [-1,-1].
'.' - дорога, 'W' - стена.
Я написал код, который основан на правиле левой руки и обозначении тупиков. Код работает, но скорость выполнения слишком большая. Необходимо ускориться примерно на 30%.
Возможно ли как то оптимизировать if/elif/else? К примеру используя словарь.

import numpy


def path_finder(maze):  
    lab = numpy.array([list(x) for x in maze.split()])  
    checked = []  
    i = 0  
    j = 0  
    size = len(lab)  
    while i != (size - 1) or j != (size - 1):  
        if (i, j) not in checked:  
            checked.append(tuple((i, j)))  
        if j + 1 < size and lab[i][j + 1] == '.' and (i, j + 1) not in checked:  
            j += 1  
        elif i + 1 < size and lab[i + 1][j] == '.' and (i + 1, j) not in checked:  
            i += 1  
        elif j - 1 > -1 and lab[i][j - 1] == '.' and (i, j - 1) not in checked:  
            j -= 1  
        elif i - 1 > -1 and lab[i - 1][j] == '.' and (i - 1, j) not in checked:  
            i -= 1  
        else:  
            checked.pop()  
            lab[i][j] = 'W'  
            if not checked:  
                return False  
            else:  
                i, j = checked[-1]  

    return True  


print(path_finder("\n".join([  
    "..W",  
    ".WW",  
    "..."])))

Answer 1

можно попробовать так изменить код:

убрать numpy за ненадобностью
список кортежей заменить на список целых чисел (позиций в массиве)
в список не добавлять и не удалять из списка элементы, а сразу сделать список размером N*N и ходить по нему вправо влево

код:

def get_pos(i, j, width):
    return i + j * width

def path_finder(maze):
    lab = [[j for j in i] for i in maze.split('\n')]
    width = len(lab)

    checked = [0 for i in range(width * width)]
    pos = 0

    i, j = 0, 0
    width = len(lab)

    while i != (width - 1) or j != (width - 1):
        if get_pos(i, j, width) not in checked[:pos]:
            checked[pos] = get_pos(i, j, width)
            pos += 1

        if j + 1 < width and lab[i][j + 1] == '.' and get_pos(i, j + 1, width) not in checked[:pos]:
            j += 1
        elif i + 1 < width and lab[i + 1][j] == '.' and get_pos(i + 1, j, width) not in checked[:pos]:
            i += 1
        elif j - 1 > -1 and lab[i][j - 1] == '.' and get_pos(i, j - 1, width) not in checked[:pos]:
            j -= 1
        elif i - 1 > -1 and lab[i - 1][j] == '.' and get_pos(i - 1, j, width) not in checked[:pos]:
            i -= 1
        else:
            pos -= 1
            if pos == 0:
                return False

            lab[i][j] = 'W'
            coord = checked[pos - 1]
            i, j = coord % width, coord // width

    return True

вариант 2:

список checked теперь используется исключительно, чтобы получить последнее положение в массиве
в проверке на направление убрана вообще проверка на наличие в списке за ненадобностью
вместо этого в клетку помещается символ '*', так что проверки на '.' уже становится достаточным и не нужно проверять что-то дополнительно

код:

def get_pos(i, j, width):
    return i + j * width

def path_finder(maze):
    lab = [[j for j in i] for i in maze.split('\n')]
    width = len(lab)

    checked = [0 for i in range(width * width)]
    pos = 0

    i, j = 0, 0
    width = len(lab)

    while i != (width - 1) or j != (width - 1):
        if get_pos(i, j, width) not in checked[:pos]:
            checked[pos] = get_pos(i, j, width)
            lab[i][j] = '*'
            pos += 1

        if j + 1 < width and lab[i][j + 1] == '.':
            j += 1
        elif i + 1 < width and lab[i + 1][j] == '.':
            i += 1
        elif j - 1 > -1 and lab[i][j - 1] == '.':
            j -= 1
        elif i - 1 > -1 and lab[i - 1][j] == '.':
            i -= 1
        else:
            pos -= 1
            if pos == 0:
                return False

            lab[i][j] = 'W'
            coord = checked[pos - 1]
            i, j = coord % width, coord // width

    return True

вариант 3:

по идее еще быстрее было бы решение, если и список lab сделать из двумерного списка одномерным и перемещаться уже в нем используя координаты как это сделано при работе со списком checked

БЛОГ НА HUSL

Есть ли выход из лабиринта?

Ответы (1 шт):