算法题：按图找最近的路（js/python3）

题目描述：
有一张 m*n 的地图，地图描述了起点和终点的位置，也描述了两点间分布的高山湖泊，高山湖泊挡住去路，需要绕道行走，请问从起点到终点的最短路径距离是多少？
注意： 走动路线只能上下左右，不能斜着走。
解法：回溯法
js版本：

var findRoute = function(start, end, grid) {
    let m = grid.length, n = grid[0].length;
    if(m === 1 && n === 1) return;
    let visited = new Array(m).fill(0).map(() => new Array(n).fill(0));
    let res = [];
    let choice = [[-1, 0],[1, 0],[0, 1],[0, -1]];
    const dfs = (cur, visited, step) => {
        let [x, y] = cur;
        if(grid[x][y] === 1) return;
        if(x === end[0] && y === end[1]){
            res.push(step);
            return;
        }
        for(let item of choice){
            let dx = x + item[0], dy = y + item[1];
            if(dx < m && dx >= 0 && dy >= 0 && dy < n){
                if(visited[dx][dy] === 1) continue;
                visited[dx][dy] = 1;
                dfs([dx, dy], visited, step+1);
                visited[dx][dy] = 0;
            }
        }
    }
    dfs(start, visited, 0);
    res.sort((a, b) => a - b);
    return res[0];
}

python3版本：

    def demo(self, grid, start, end):
        '''
        按图找最近的路
        '''
        m, n = len(grid), len(grid[0])
        # 只有一个格子，直接退出
        if m == 1 and n == 1:
            return 0
        # 表示是否已访问过。0：未访问；1：已访问。
        visited = [[0 for _ in range(m)] for _ in range(n)]
        # 存放从起点到终点的所有可能步数
        result = []
        
        def bfs(current, visited, step):
            '''
            回溯
            current：当前的坐标
            visited：记录已访问的数组
            step：从起点到当前坐标所用的步数
            '''
            x, y = current
            # 如果是湖泊就直接返回
            if grid[x][y] == 1:
                return
            # 判断到达目的地
            if x == end[0] and y == end[1]:
                # 直接将结果存下（这里可以做优化）
                result.append(step)
                # 直接返回，后续操作不需要执行
                return

            # 遍历四个方向
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                # 计算出遍历后的新坐标
                nx, ny = x + dx, y + dy
                # 保证新坐标不超出二维数组范围
                if 0 <= nx < m and 0 <= ny < n:
                    # 如果新坐标在之前已经被访问过，就跳过
                    if visited[nx][ny] == 1:
                        continue
                    # 否则可以进入回溯
                    # 将当前坐标标记为已访问
                    visited[nx][ny] = 1
                    # 进入回溯，注意部署step要+1
                    bfs((nx, ny), visited, step+1)
                    # 撤销标记，重回未访问
                    visited[nx][ny] = 0

        # 执行回溯算法
        bfs(start, visited, 0)
        # 上面得到的结果是乱序的，为了获得最小步数，这里执行升序排序
        # （如果上面做了优化，这步其实不需要）
        result.sort()
        # 返回结果
        # 数组的count方法可以获得指定元素的数量
        return result[0]