苦海

学海无涯苦做舟

0%

Python Challenge (Level 24)

发表于 更新于 Valine：

第24关

这一关是一张迷宫图片，看来是要解这个迷宫。

根据网页标题，迷宫是from top to bottom，黑色像素是路径，白色像素是墙。这张图片大小为641×641，入口在右上角(0, 639)， 出口是左下角(640, 1)。

解迷宫可以用BFS，也可以用DFS，但DFS不能保证是最短的路径。我用的是BFS. 查了下网上其他人的攻略，发现DFS也能得到同样结果，看来应该是只有一条路径吧。

迷宫的路径的Green、Blue通道都是0，而Red通道会0和非0交替。把非0值收集起来，写到文件，就可以得到zip文件。解压后，得到一张图片，包含通关信息——lake。里面还有mybroken.zip，暂时不知道有何用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# -*- coding:utf-8 -*-

from PIL import Image
import numpy as np

def BFS(imdata, startPos, endPos):
    ''' 广度优先搜索迷宫路径
    :param imdata:  迷宫图片像素值, (height, width, channel)
    :param startPos:  起始坐标, [x, y]
    :param endPos:  终止坐标, [x, y]
    :return: 返回记录父坐标的矩阵，上右下左分别用0, 1, 2, 3表示。
             根据这个矩阵，可回溯得到最短路径。
    '''
    visited = np.zeros(imdata.shape[0 : 2], dtype=np.False_)
    visited[0, 639] = True
    visited[640, 1] = True
    father = -np.ones(imdata.shape[0 : 2], dtype=np.int8)
    dx = [-1, 0, 1, 0] #上右下左
    dy = [0, 1, 0, -1]
    bfs_queue = []
    bfs_queue.append(startPos)
    while bfs_queue:
        cur_pos = bfs_queue.pop(0)
        if cur_pos == endPos:
            break
        for i in range(4):
            x = cur_pos[0] + dx[i]
            y = cur_pos[1] + dy[i]
            if imdata[x, y, 1] == imdata[x, y, 2] == 0 and not visited[x, y]:
                father[x, y] = i
                bfs_queue.append([x, y])
        visited[cur_pos[0], cur_pos[1]] = True
    return father

def mapXY(pre, pos):
    ''' 根据父坐标类型和当前坐标，得到父坐标
    :param pre: 0,1,2,3分别表示当前坐标位于父坐标的上右下左
    :param pos: 当前坐标[x, y]
    :return: 父坐标[x, y]
    '''
    if pre == 0:
        pos[0] += 1
    elif pre == 1:
        pos[1] -= 1
    elif pre == 2:
        pos[0] -= 1
    elif pre == 3:
        pos[1] += 1
    else:
        raise Exception("Invalid Father Pos!")
    return pos

def getData(imdata, father, startPos, endPos):
    ''' 回溯得到最短路径以及路径上每个像素点r通道的像素值
    :param imdata: 迷宫图片像素值
    :param father: 每个点的父坐标
    :param startPos: 开始坐标 [x, y]
    :param endPos: 结束坐标 [x, y]
    :return: Red通道像素值, 用绿色像素标记的迷宫路径
    '''
    data = []
    curPos = endPos[:]
    while curPos != startPos:
        #取Red通道像素值
        data.append(chr(imdata[curPos[0], curPos[1], 0]))
        #路径用绿色像素标记
        imdata[curPos[0], curPos[1]] = [0, 255, 0, 255]
        curPos = mapXY(father[curPos[0], curPos[1]], curPos)
    data.append(chr(imdata[startPos[0], startPos[1], 0]))
    return data, imdata

def solve():
    im = Image.open('maze.png')
    w, h = im.size
    imdata = list(im.getdata())
    imdata = np.array(imdata)
    imdata = imdata.reshape((h, w, -1))
    print "BFS"
    fatherMat = BFS(imdata, [1, 639], [639, 1])
    print "Get Path and data"
    data, nimdata = getData(imdata, fatherMat, [1, 639], [639, 1])
    open('maze.zip', 'w').write(''.join(data[::-2]))

    nimdata = nimdata.reshape((-1, 4)).tolist()
    nimdata = [tuple(x) for x in nimdata]
    im.putdata(nimdata)
    im.save('mazeSolve.jpg')

if __name__ == "__main__" : solve()

下一关 http://www.pythonchallenge.com/pc/hex/lake.html