python/bfs_maze.py at master · junishitsuka/python · GitHub

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
# coding: UTF-8
# pythonのversion対応
try:
    from Queue import Queue
except ImportError:
    from queue import Queue

def checkio(maze_map):
    start = [1, 1]
    end = [10, 10]
    q = Queue()
    visited = {}
    parent = {}
    str = ''
    visited["%d,%d" % (start[0],start[1])] = True
    parent["%d,%d" % (start[0],start[1])] = None
    q.put(start)
    while (not(q.empty())):
        tmp = q.get()
        if (tmp == end): break
        up = [(tmp[0] - 1), tmp[1]]
        down = [(tmp[0] + 1), tmp[1]]
        right = [tmp[0], (tmp[1] + 1)]
        left = [tmp[0], (tmp[1] -1)]
        if (maze_map[up[0]][up[1]] == 0 and visited.get("%d,%d" % (up[0],up[1])) != True):
            visited["%d,%d" % (up[0],up[1])] = True
            q.put(up)
            parent["%d,%d" % (up[0],up[1])] = tmp
        if (maze_map[down[0]][down[1]] == 0 and visited.get("%d,%d" % (down[0],down[1])) != True):
            visited["%d,%d" % (down[0],down[1])] = True
            q.put(down)
            parent["%d,%d" % (down[0],down[1])] = tmp
        if (maze_map[right[0]][right[1]] == 0 and visited.get("%d,%d" % (right[0],right[1])) != True):
            visited["%d,%d" % (right[0],right[1])] = True
            q.put(right)
            parent["%d,%d" % (right[0],right[1])] = tmp
        if (maze_map[left[0]][left[1]] == 0 and visited.get("%d,%d" % (left[0],left[1])) != True):
            visited["%d,%d" % (left[0],left[1])] = True
            q.put(left)
            parent["%d,%d" % (left[0],left[1])] = tmp

    target = [end[0], end[1]]
    while (not(parent.get("%d,%d" % (target[0],target[1])) == None)):
        par = parent["%d,%d" % (target[0],target[1])]
        if (target[0] == par[0] + 1): str = 'S' + str
        if (target[0] == par[0] - 1): str = 'N' + str
        if (target[1] == par[1] + 1): str = 'E' + str
        if (target[1] == par[1] - 1): str = 'W' + str
        target = par

    print str

    return str

# test
checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])