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

Question

给定一个宽度不同的路径网格，我如何找到通向终点的路径？

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

21111111100000
00000011000000
00001111111111
00001111100111
00001110000101
00001111100113

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

已编辑:路径不应包含不必要的“浪费”步行，这意味着如果垂直路径的宽度为 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,'')

让它在找到解决方案后立即停止的优化留给读者作为练习(您可以让 flood 返回一个 bool 值以指示它是否找到了某些东西，或者使用全局标志)。

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

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

对于它的值(value)，只是为了表明广度优先搜索并不那么复杂，一个实际的 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***