DjangoBB LoFi version

Полная версия: Найти выход из лабиринта.

Начало » Центр помощи » Найти выход из лабиринта.

kozlo22

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

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

[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

Почему? Я не могу понять.

sp3

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

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

kozlo22

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

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 23:59:47

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

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

Ну и т.д.

FishHook

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

Потому что из 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)

kozlo22

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

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

kozlo22

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

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