all_paths.py

"""这是所有路径的解法"""
_grids = [[3, 5, 1],
          [2, 1, 5],
          [4, 2, 1]]

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]


class Path():

    def __init__(self, grids):
        self._path = set()
        self._grids = grids

    def neighbor(self, point, direction):
        x = point[0] + direction[0]
        y = point[1] + direction[1]    
        if x < 0 or y < 0 or x > (len(self._grids)-1) or y > (len(self._grids[0])-1):
            return None
        else:
            return (x, y)


    def height(self, point):
        return self._grids[point[0]][point[1]]
    
    def find_low(self, current):
        self._path.add(current)
        for direction in directions:
            nb_point = self.neighbor(current, direction)
            
            if nb_point and (self.height(nb_point) <= self.height(current)): # 洼地
                if nb_point not in self._path:
                    self._path.add(nb_point)
                    self.find_low(nb_point)

path = Path(_grids)
path.find_low((0, 0))
assert path._path == {(0, 0), (1, 0), (1, 1)}

bigger_pool = [[8, 5, 4, 2, 4],
               [2, 3, 5, 2, 3],
               [4, 2, 1, 1, 5]]
bigger_pool_path = Path(bigger_pool)
bigger_pool_path.find_low((0, 0))
assert bigger_pool_path._path == {
    (0, 0), (0, 1), (0, 2), (0, 3),
    (1, 0), (1, 1), (1, 3),
    (2, 1), (2, 2), (2, 3)
}

first_path.py

"""
题目没记清楚，不过似乎是根据格子周围格子的高度根据深度确定流水方向，大概想法是深度优先遍历
"""

grids = [[3, 5, 1],
         [2, 1, 5],
         [4, 2, 1]]

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def neighbor(point, direction):
    x = point[0] + direction[0]
    y = point[1] + direction[1]    
    if x < 0 or y < 0 or x > 2 or y > 2:
        return None
    else:
        return (x, y)


def height(point):
    return grids[point[0]][point[1]]


start = (0, 0)
path = [start]


def find_path():
    point = start
    while True:
        for direction in directions:
            nb_point = neighbor(point, direction)
            if nb_point is None:
                continue
            if height(nb_point) < height(point): # 邻居是洼地
                path.append(nb_point)
                point = nb_point
                break                            # 跳出当前格子的循环，进入下一个格子的循环
        else:                                    # 四周都比当前格子高，跳出 while 循环
            break
find_path()
assert path == [(0, 0), (1, 0), (1, 1)]          # 找到的第一条路径