python迷宮，顯示所有走的路線，包括死路，用箭頭顯示所有正確路線

# 定義迷宮，1為通路，0為墻，網上的演算法有問題，而且只能輸出一種情況

# 經過我改編，該演算法可以輸出所有情況和可行的方法數，并且輸出程序和每一種方法

# 此演算法和判斷洼地匯水區域演算法有關，后者撰寫的依據是此演算法

maze = [[1, 0, 1, 0, 0, 1, 1, 0, 1, 1],

        [1, 1, 1, 1, 1, 0, 1, 0, 0, 1],

        [0, 0, 1, 0, 1, 0, 1, 0, 0, 1],

        [0, 1, 1, 1, 1, 0, 1, 0, 0, 1],

        [0, 0, 1, 0, 1, 0, 1, 0, 1, 1],

        [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],

        [1, 1, 1, 1, 1, 0, 1, 0, 0, 1],

        [1, 1, 0, 0, 1, 0, 1, 1, 1, 1],

        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1],

        [1, 0, 1, 0, 1, 0, 1, 1, 0, 1]]





# 判斷坐標的有效性，如果超出陣列邊界或是不滿足值為1的條件，說明該點無效回傳False，否則回傳True。

def check(x, y):

    if y >= 0 and y < len(maze) and x >= 0 and x < len(maze[0]) and maze[y][x] == 1:

        return True

    else:

        return False





def walk(x, y):  # 走迷宮的演算法

    global success, procedure_list, success_count  # 宣告這些變數用全域的



    maze[y][x] = 0  # 已經走過需要標記，因為不能再走，否則兜圈子

    procedure_list.append((x, y))  # 程序串列加入該點坐標

    if x == 9 and y == 0:  # 如果到達終點（9，0）

        print("success")  # 輸出“成功”

        success = 1  # 表示能走通

        success_count += 1  # 成功的方法數增加1

        success_procedure_ls.append(list(procedure_list))  # 保存成功路徑

        procedure_list.remove((x, y))

        maze[y][x] = 1  # 設為通路

        return True

    if maze[y][x] == 0:

        print("第{}行，第{}列".format(y + 1, x + 1))

        for pos_y, pos_x in pos_ls:

            if check(x + pos_x, y + pos_y): break

        else:

            print("死路")

    if success < 100:



        for pos_y, pos_x in pos_ls:



            if check(x + pos_x, y + pos_y):

                walk(x + pos_x, y + pos_y)



        maze[y][x] = 1

        procedure_list.remove((x, y))



    return success





procedure_list = []

success = 0  # 是否成功

success_procedure_ls = []  # 成功方法的串列

success_count = 0  # 成功方法數，初始為0

pos_ls = [(0, -1), (-1, 0), (0, 1), (1, 0)]  # 分別代表上，左，下，右

walk(0, 9)  # 從（0，9）出發

# print(procedure_list)





# for way in success_procedure_ls:

#     print(way)

maze_copy = list(maze)  # 一個迷宮的淺復制（最外層為深復制）



x, y = 0, 1  # x代表橫坐標，y代表縱坐標

n_way = 0

for way in success_procedure_ls:

    i = 0

    n_way += 1

    print("第{}種方法：".format(n_way))

    print(way)  # 輸出方法

    for line in maze_copy:

        maze[i] = list(maze_copy[i])  # 一個迷宮的深復制

        i += 1  # i指向下一行

    for index in range(len(way) - 1):  # 把每一步轉化為箭頭

        if way[index + 1][x] == way[index][x] - 1:

            maze[way[index][y]][way[index][x]] = "←"

        elif way[index + 1][x] == way[index][x] + 1:

            maze[way[index][1]][way[index][0]] = "→"

        elif way[index + 1][y] == way[index][y] - 1:

            maze[way[index][y]][way[index][x]] = "↑"

        elif way[index + 1][y] == way[index][y] + 1:

            maze[way[index][1]][way[index][0]] = "↓"

    for row in maze:

        for item in row:

            if item not in [0, 1]:

                print(item, end='')

            else:

                print(str(item) + ' ', end='')

        print()

    print('*  ' * 100)  # 分開每一種方法

print("一共{}中方法".format(success_count))  # 輸出方法數

D:\Users\jjh\AppData\Local\Programs\Python\Python35\python.exe D:/Users/jjh/PycharmProjects/untitled/maze_new.py

第10行，第1列

第9行，第1列

第8行，第1列

第7行，第1列

第6行，第1列

死路

第7行，第2列

第7行，第3列

第7行，第4列

第6行，第4列

第6行，第5列

第5行，第5列

第4行，第5列

第4行，第4列

第4行，第3列

第4行，第2列

死路

第3行，第3列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第2行，第4列

第2行，第5列

第3行，第5列

死路

第5行，第3列

死路

第3行，第5列

第2行，第5列

第2行，第4列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第3行，第3列

第4行，第3列

第4行，第2列

死路

第4行，第4列

死路

第5行，第3列

死路

第6行，第6列

第6行，第7列

第5行，第7列

第4行，第7列

第3行，第7列

第2行，第7列

第1行，第7列

第1行，第6列

死路

第6行，第8列

死路

第7行，第7列

第8行，第7列

第8行，第8列

第8行，第9列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第9行，第10列

第9行，第9列

死路

第10行，第10列

死路

第9行，第9列

第9行，第10列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第10行，第10列

死路

第9行，第7列

第10行，第7列

第10行，第8列

死路

第7行，第5列

第8行，第5列

第9行，第5列

第10行，第5列

死路

第7行，第5列

第6行，第5列

第6行，第4列

死路

第5行，第5列

第4行，第5列

第4行，第4列

第4行，第3列

第4行，第2列

死路

第3行，第3列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第2行，第4列

第2行，第5列

第3行，第5列

死路

第5行，第3列

死路

第3行，第5列

第2行，第5列

第2行，第4列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第3行，第3列

第4行，第3列

第4行，第2列

死路

第4行，第4列

死路

第5行，第3列

死路

第6行，第6列

第6行，第7列

第5行，第7列

第4行，第7列

第3行，第7列

第2行，第7列

第1行，第7列

第1行，第6列

死路

第6行，第8列

死路

第7行，第7列

第8行，第7列

第8行，第8列

第8行，第9列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第9行，第10列

第9行，第9列

死路

第10行，第10列

死路

第9行，第9列

第9行，第10列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第10行，第10列

死路

第9行，第7列

第10行，第7列

第10行，第8列

死路

第8行，第5列

第9行，第5列

第10行，第5列

死路

第8行，第2列

死路

第8行，第2列

第7行，第2列

第7行，第1列

第6行，第1列

死路

第7行，第3列

第7行，第4列

第6行，第4列

第6行，第5列

第5行，第5列

第4行，第5列

第4行，第4列

第4行，第3列

第4行，第2列

死路

第3行，第3列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第2行，第4列

第2行，第5列

第3行，第5列

死路

第5行，第3列

死路

第3行，第5列

第2行，第5列

第2行，第4列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第3行，第3列

第4行，第3列

第4行，第2列

死路

第4行，第4列

死路

第5行，第3列

死路

第6行，第6列

第6行，第7列

第5行，第7列

第4行，第7列

第3行，第7列

第2行，第7列

第1行，第7列

第1行，第6列

死路

第6行，第8列

死路

第7行，第7列

第8行，第7列

第8行，第8列

第8行，第9列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第9行，第10列

第9行，第9列

死路

第10行，第10列

死路

第9行，第9列

第9行，第10列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第10行，第10列

死路

第9行，第7列

第10行，第7列

第10行，第8列

死路

第7行，第5列

第8行，第5列

第9行，第5列

第10行，第5列

死路

第7行，第5列

第6行，第5列

第6行，第4列

死路

第5行，第5列

第4行，第5列

第4行，第4列

第4行，第3列

第4行，第2列

死路

第3行，第3列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第2行，第4列

第2行，第5列

第3行，第5列

死路

第5行，第3列

死路

第3行，第5列

第2行，第5列

第2行，第4列

第2行，第3列

第2行，第2列

第2行，第1列

第1行，第1列

死路

第1行，第3列

死路

第3行，第3列

第4行，第3列

第4行，第2列

死路

第4行，第4列

死路

第5行，第3列

死路

第6行，第6列

第6行，第7列

第5行，第7列

第4行，第7列

第3行，第7列

第2行，第7列

第1行，第7列

第1行，第6列

死路

第6行，第8列

死路

第7行，第7列

第8行，第7列

第8行，第8列

第8行，第9列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第9行，第10列

第9行，第9列

死路

第10行，第10列

死路

第9行，第9列

第9行，第10列

第8行，第10列

第7行，第10列

第6行，第10列

第5行，第10列

第5行，第9列

死路

第4行，第10列

第3行，第10列

第2行，第10列

success

第10行，第10列

死路

第9行，第7列

第10行，第7列

第10行，第8列

死路

第8行，第5列

第9行，第5列

第10行，第5列

死路

第1種方法：

[(0, 9), (0, 8), (0, 7), (0, 6), (1, 6), (2, 6), (3, 6), (3, 5), (4, 5), (5, 5), (6, 5), (6, 6), (6, 7), (7, 7), (8, 7), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]

1 0 1 0 0 1 1 0 1 1 

1 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 0 ↑

0 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 1 ↑

1 0 0 →→→↓1 0 ↑

→→→↑1 0 ↓0 0 ↑

↑1 0 0 1 0 →→→↑

↑0 1 0 1 0 1 0 1 1 

↑0 1 0 1 0 1 1 0 1 

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  

第2種方法：

[(0, 9), (0, 8), (0, 7), (0, 6), (1, 6), (2, 6), (3, 6), (3, 5), (4, 5), (5, 5), (6, 5), (6, 6), (6, 7), (7, 7), (8, 7), (8, 8), (9, 8), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]

1 0 1 0 0 1 1 0 1 1 

1 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 0 ↑

0 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 1 ↑

1 0 0 →→→↓1 0 ↑

→→→↑1 0 ↓0 0 ↑

↑1 0 0 1 0 →→↓↑

↑0 1 0 1 0 1 0 →↑

↑0 1 0 1 0 1 1 0 1 

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  

第3種方法：

[(0, 9), (0, 8), (0, 7), (0, 6), (1, 6), (2, 6), (3, 6), (4, 6), (4, 5), (5, 5), (6, 5), (6, 6), (6, 7), (7, 7), (8, 7), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]

1 0 1 0 0 1 1 0 1 1 

1 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 0 ↑

0 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 1 ↑

1 0 0 1 →→↓1 0 ↑

→→→→↑0 ↓0 0 ↑

↑1 0 0 1 0 →→→↑

↑0 1 0 1 0 1 0 1 1 

↑0 1 0 1 0 1 1 0 1 

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  

第4種方法：

[(0, 9), (0, 8), (0, 7), (0, 6), (1, 6), (2, 6), (3, 6), (4, 6), (4, 5), (5, 5), (6, 5), (6, 6), (6, 7), (7, 7), (8, 7), (8, 8), (9, 8), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]

1 0 1 0 0 1 1 0 1 1 

1 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 0 ↑

0 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 1 ↑

1 0 0 1 →→↓1 0 ↑

→→→→↑0 ↓0 0 ↑

↑1 0 0 1 0 →→↓↑

↑0 1 0 1 0 1 0 →↑

↑0 1 0 1 0 1 1 0 1 

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  

第5種方法：

[(0, 9), (0, 8), (0, 7), (1, 7), (1, 6), (2, 6), (3, 6), (3, 5), (4, 5), (5, 5), (6, 5), (6, 6), (6, 7), (7, 7), (8, 7), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]

1 0 1 0 0 1 1 0 1 1 

1 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 0 ↑

0 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 1 ↑

1 0 0 →→→↓1 0 ↑

1 →→↑1 0 ↓0 0 ↑

→↑0 0 1 0 →→→↑

↑0 1 0 1 0 1 0 1 1 

↑0 1 0 1 0 1 1 0 1 

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  

第6種方法：

[(0, 9), (0, 8), (0, 7), (1, 7), (1, 6), (2, 6), (3, 6), (3, 5), (4, 5), (5, 5), (6, 5), (6, 6), (6, 7), (7, 7), (8, 7), (8, 8), (9, 8), (9, 7), (9, 6), (9, 5), (9, 4), (9, 3), (9, 2), (9, 1), (9, 0)]

1 0 1 0 0 1 1 0 1 1 

1 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 0 ↑

0 1 1 1 1 0 1 0 0 ↑

0 0 1 0 1 0 1 0 1 ↑

1 0 0 →→→↓1 0 ↑

1 →→↑1 0 ↓0 0 ↑

→↑0 0 1 0 →→↓↑

↑0 1 0 1 0 1 0 →↑

↑0 1 0 1 0 1 1 0 1 

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  

標籤：腳本語言(Perl/Python)

上一篇：求做一個能群發Imessage的軟體

下一篇：xpath如何處理子節點