Algorithm/minpath.py at master · sulei1324/Algorithm · 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
69
70
71
72
73
74
75
__author__ = 'Su Lei'

import copy

def print_path(m):
    global w, h
    for i1 in xrange(h):
        s = ""
        for j1 in xrange(w):
            if [i1, j1] not in m:
                if map_i[i1][j1] == 1:
                    s += " # "
                else:
                    s += " * "
            else:
                s += " - "
        print s

# map_i = [[0, 0, 0, 1, 0],
#          [0, 1, 0, 1, 0],
#          [1, 0, 0, 0, 0],
#          [0, 0, 1, 0, 1],
#          [0, 0, 0, 0, 0]]

map_i = [[0, 0, 1, 0],
         [0, 0, 0, 0],
         [0, 0, 1, 0],
         [0, 1, 0, 0],
         [0, 0, 0, 1]]

h = len(map_i)
w = len(map_i[0])
data_i = []
for i in xrange(h):
    data_i.append([0]*w)

step = 1
path = []
min_step = 99999
min_path = []


ini_location = [0, 0]
dest_location = [3, 2]

def dfs(l, s):
    print path
    global min_path, min_step
    next_step = ((0, 1), (1, 0), (0, -1), (-1, 0))
    x = l[0]
    y = l[1]
    if x == dest_location[0] and y == dest_location[1]:
        # print_path(path)
        # print path
        if s < min_step:
            min_step = s
            min_path = copy.deepcopy(path)
        return
    for j in next_step:
        nx = j[0] + x
        ny = j[1] + y
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        if map_i[nx][ny] != 1 and data_i[nx][ny] == 0:
            s += 1
            data_i[nx][ny] = 1
            path.append([nx, ny])
            dfs([nx, ny], s)
            path.pop()
            data_i[nx][ny] = 0
            s -= 1

data_i[ini_location[0]][ini_location[1]] = 1
path.append(ini_location)
dfs(ini_location, step)