Уведомления

Группа в Telegram: @pythonsu

#1 Дек. 22, 2013 02:15:48

kozlo22
От: Беларусь, Минск
Зарегистрирован: 2012-11-01
Сообщения: 115
Репутация: +  0  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

Задача такая: дан лабиринт в вида:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
    [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
Найти выход. Начальная точка 
[1,1]
, конечная 
[10,10]
В результате должны получить строку состоящую из букв, указывающих направление движения: S - south, W - west…
Вот я тут что-то понаписывал.
def searchway(lab):
    x = 1
    y = 1
    res = ''
    while x != 10 and y != 10:
        for i in range(1, 11):
            for j in range(1,11):
                if lab[i - x][j] == 1 and lab[i][j - y] == 1:
                     y += 1
                     res += 'E'
                if lab[i - x][j] == 1 and lab[i][j - y] == 1 and lab[i][j + y] == 1:
                     x += 1
                     res += 'S'
                if lab[i - x][j] == 1 and lab[i][j + y] == 1:
                     y -= 1
                     res += 'W'
                if lab[i + x][j] == 1 and lab[i][j - y] == 1 and lab[i][j + y] == 1:
                     x -= 1
                     res += 'N'
    return(res)
В строке 
if lab[i - x][j] == 1 and lab[i][j + y] == 1:
Возникает исключение 
list index out of range
Почему? Я не могу понять.

Отредактировано kozlo22 (Дек. 22, 2013 17:29:40)

Офлайн

#2 Дек. 22, 2013 07:32:09

sp3
От:
Зарегистрирован: 2010-01-12
Сообщения: 405
Репутация: +  18  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

Ну так принтуйте все значения что бы понять как работает Ваш код.
А вообще все придумано до нас.



Офлайн

#3 Дек. 22, 2013 18:37:18

kozlo22
От: Беларусь, Минск
Зарегистрирован: 2012-11-01
Сообщения: 115
Репутация: +  0  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

sp3
я изучал алгоритм А*.
Но пока реализовать его не могу.
Т.к. лабиринт представлен в виде набор единиц и нулей, то можно сделать проще, позже уже попытаться сделать красиво и правильно)
Карочь, вот вывод значений x,y и res на каждой итерации.

1 5
EEEE
1 6
2 6
2 5
EEEEESW
2 4
EEEEESWW
2 3
EEEEESWWW
2 2
EEEEESWWWW
2 1
EEEEESWWWWW
2 0
EEEEESWWWWWW
EEEEESWWWWWW
2 1
2 0
1 0
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
EEEEESWWWWWWEWN
1 1
EEEEESWWWWWWEWNE
1 2
EEEEESWWWWWWEWNEE
1 3
EEEEESWWWWWWEWNEEE
1 4
EEEEESWWWWWWEWNEEEE
1 5
1 4
EEEEESWWWWWWEWNEEEEEW
1 3
EEEEESWWWWWWEWNEEEEEWW
EEEEESWWWWWWEWNEEEEEWW

Отредактировано kozlo22 (Дек. 22, 2013 19:06:04)

Офлайн

#4 Дек. 22, 2013 23:59:47

kozlo22
От: Беларусь, Минск
Зарегистрирован: 2012-11-01
Сообщения: 115
Репутация: +  0  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

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

def searchway(lab):
    x = 1
    y = 1
    res = ''
    while x < 10 and y < 10:
            if lab[x - 1][y] == 1 and lab[x][y - 1] == 1:
                y += 1
                res += 'E'
                print(x, y)
            if lab[x - 1][y] == 1 and lab[x][y - 1] == 1 and lab[x][y + 1] == 1:
                x += 1
                res += 'S'
                print(x, y)
            if lab[x - 1][y] == 1 and lab[x][y + 1] == 1:
                y -= 1
                res += 'W'
                print(x, y)
            if lab[x + 1][y] == 1 and lab[x][y - 1] == 1 and lab[x][y + 1] == 1:
                x -= 1
                res += 'N'
                print(x, y)
            print(res)
    return(res)

1 2
E
E
E
E
E
E
E
E
E
E
E
E
E
Ну и т.д.

Офлайн

#5 Дек. 23, 2013 04:31:16

FishHook
От:
Зарегистрирован: 2011-01-08
Сообщения: 8312
Репутация: +  568  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

Потому что из 4х if не отрабатывает ни один, соответственно значения x и y не изменяются.
Запустите вот это, будет понятнее

def searchway(lab):
    x = 1
    y = 1
    res = ''
    while x < 10 and y < 10:
            if lab[x - 1][y] == 1 and lab[x][y - 1] == 1:
                y += 1
                res += 'E'
                print(x, y)
            elif lab[x - 1][y] == 1 and lab[x][y - 1] == 1 and lab[x][y + 1] == 1:
                x += 1
                res += 'S'
                print(x, y)
            elif lab[x - 1][y] == 1 and lab[x][y + 1] == 1:
                y -= 1
                res += 'W'
                print(x, y)
            elif lab[x + 1][y] == 1 and lab[x][y - 1] == 1 and lab[x][y + 1] == 1:
                x -= 1
                res += 'N'
                print(x, y)
            else:
                print "NO WAY"
            print(res)
    return(res)



Офлайн

#6 Дек. 23, 2013 13:48:18

kozlo22
От: Беларусь, Минск
Зарегистрирован: 2012-11-01
Сообщения: 115
Репутация: +  0  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

FishHook, пробовал, все равно зацикливается.

Офлайн

#7 Дек. 23, 2013 14:15:38

kozlo22
От: Беларусь, Минск
Зарегистрирован: 2012-11-01
Сообщения: 115
Репутация: +  0  -
Профиль   Отправить e-mail  

Найти выход из лабиринта.

Обрабатывается только первый if и ветка else.

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version