算法：具有可变路径宽度的路径查找

Question

给定一个宽度不同的路径网格，我怎样才能找到一条通向终点的路径？

路径将由二维数组表示，其中 0 表示不能行走，1 表示可以行走，2 表示起点，3 表示终点。考虑以下示例：

21111111100000
00000011000000
00001111111111
00001111100111
00001110000101
00001111100113

在上面的示例中，路径的宽度从 1 到 3 不等，并且存在许多可以通向终点的解决方案。我想找到一条通向它的路径，路径不一定是最短的（也不应该是最长的）。每条路径的宽度是未知的，这意味着网格可以是除起点和终点之外的所有“1”。

已编辑：路径不应包含不必要的 "wasted" 步行，这意味着如果垂直路径的宽度为 2，则结果不应只是沿着路径走，然后向右走一步，然后一直向上走

Answer 1

我同意 Calumn 的观点：DFS 是这里最简单的方法。这是一个类似于 python 的伪代码的简单解决方案。它会将解决方案打印为 'L'、'R'、U'、'D' 的序列，以指示左、右、上或下。

def flood(x,y,story):
  if (visited[x][y] or map[x][y]=='0'): return;
  visited[x][y]=True;
  if (map[x][y]=='3'): 
    print 'done. The path is: '+story
    return
  if (x<len(a[0])): flood(x+1,y,story+'R')
  if (y<len(a)): flood(x,y+1,story+'D')
  if (x>0): flood(x-1,y,story+'L')
  if (y>0): flood(x,y-1,story+'U')

def solve(map):
  visited = array_of_false_of_same_size_as(map)
  x,y = find_the_two(map)
  flood(x,y,'')

一旦找到解决方案就让它停止的优化留作 reader 的练习（您可以将 flood return 设置为布尔值以指示它是否找到了某些东西，或者使用全局标志）。

(p.s。我制作了这个答案社区维基，因为我只是在澄清 Calumn 的答案。我不能要求太多的功劳)

广度优先搜索版本，也在Python

对于它的价值，只是为了表明广度优先搜索并不那么复杂，Python 中的实际可运行程序：

def find(grid, xstart=0, ystart=0):
  # Maps (xi,yi) to (x(i-1), y(i-1))
  prev = {(xstart, ystart):None}

  # Prepare for the breadth-first search
  queue = [(xstart, ystart)]
  qpos = 0
  # Possibly enqueue a trial coordinate
  def enqueue(prevxy, dx, dy):
    x = prevxy[0] + dx
    y = prevxy[1] + dy
    xy = (x, y)
    # Check that it hasn't been visited and the coordinates
    # are valid and the grid position is not a 0
    if (xy not in prev
        and x >= 0 and x < len(grid)
        and y >= 0 and y < len(grid[x])
        and grid[x][y] != 0):
      # Record the history (and the fact that we've been here)
      prev[xy] = prevxy
      # If we found the target, signal success
      if grid[x][y] == 3:
        return xy
      # Otherwise, queue the new coordinates
      else:
        queue.append(xy)
        return None

  # The actual breadth-first search
  while qpos < len(queue):
    xy = queue[qpos]
    qpos += 1
    found = (  enqueue(xy, 1, 0)
            or enqueue(xy, 0, 1)
            or enqueue(xy, -1, 0)
            or enqueue(xy, 0, -1))
    if found: break

  # Recover the path
  path = []
  while found:
    path.append(found)
    found = prev[found]
  path.reverse()
  return path

# Test run    
grid = [ [2,1,1,1,1,1,1,1,1,0,0,0,0,0]
       , [0,0,0,0,0,0,1,1,0,0,0,0,0,0]
       , [0,0,0,0,1,1,1,1,1,1,1,1,1,1]
       , [0,0,0,0,1,1,1,1,1,0,0,1,1,1]
       , [0,0,0,0,1,1,1,0,0,0,0,1,0,1]
       , [0,0,0,0,1,1,1,1,1,0,0,1,1,3]
       ]
for x, y in find(grid): grid[x][y]='*'
print '\n'.join(''.join(str(p) for p in line) for line in grid)

输出：

*******1100000
000000*1000000
000011******11
00001111100*11
00001110000*01
00001111100***

算法：具有可变路径宽度的路径查找

Algorithm: path finding with variable path width

algorithm

path-finding

广度优先搜索版本，也在Python