如何在X * Y网格中找到最短路径

Question

我在Python中有一个网格N * M。

其中“ X”代表边界，

“ 1”代表当前位置，

“ 2”代表完成

和“ 3”表示禁止的位置。

最后一件事是（假设你是一辆汽车）你只能坐直或向右行驶。

示例3x3，边框除外：

[X,X,X,X,X]
[X,2,1,0,X]
[X,0,3,0,X]
[X,0,0,0,X]
[X,X,X,X,X]

另一个例子：

[X,X,X,X,X]
[X,2,0,0,X]
[X,3,3,1,X]
[X,X,X,X,X]

或另一个：

[X,X,X,X,X,X,X]
[X,0,2,0,0,0,X]
[X,0,3,0,3,0,X]
[X,0,0,0,0,0,X]
[X,0,3,0,3,0,X]
[X,0,3,1,3,0,X]
[X,X,X,X,X,X,X]

您对将找到最快方法的具体脚本有什么建议吗？

如果没有，请打印（“无解决方案”）？

非常感谢！

为了帮助您了解以下情况：picture of example 1 and 2

Answer 1

这很有趣。蛮力方法会计算出系统中所有可能的路径，最后找到以2结尾的路径的最小路径长度。请注意，init只是返回一个有效的矩阵进行运算。如果找不到矩阵的解，则solve函数将返回None。

BLOCK=3
FINAL=2
TERMINATE=None

def init(n,m):
  # returns array with essential components, but not necessarily with solution
  import numpy
  import random
  while True:
    try:
      a=numpy.zeros((n,m),dtype=int)
      for i in range(n):
        for j in range(m):
          t=1
          while t==1: t=numpy.random.randint(0,3)
          a[i,j]=t
      c=random.choice(list(zip(*(a==0).nonzero())))
      a[c]=1
      twos=list(zip(*(a==2).nonzero()))
      c=random.choice(twos)
      for i in twos:
        if i!=c: a[i]=3
      break
    except:
      continue
  return a

def possible_moves(a,pos):
  n,m=a.shape
  test_moves=[(0,1),(1,0),(-1,0),(0,-1)]
  #print('from pos={}'.format(pos))
  x,y=pos[0:2]
  valid_moves=[]
  for t in test_moves:
    new=(t[0]+x,t[1]+y)
    if t[0]+x>-1 and \
       t[0]+x<n and \
       t[1]+y>-1 and \
       t[1]+y<m:
      if a[new] not in [BLOCK]:
        valid_moves.append((t[0]+x,t[1]+y))
  return valid_moves

def allpaths(a,paths):
  for path in paths:
    #print('-{}'.format(path))
    if path[-1] in [TERMINATE,FINAL]: continue
    pos=path[-1]
    moves=possible_moves(a,pos)
    if not moves:
      path.append(TERMINATE)
      continue
    base=path.copy()
    for im,move in enumerate(moves):
      b=a.copy()
      #print('set pos {} to block'.format(pos))
      b[pos]=BLOCK
      if im==0:
        if a[move]==FINAL: path.append(FINAL)
        else: path.append(move)
      else:
        if a[move]==FINAL: paths.append(base+[FINAL])
        else: paths.append(base+[move])
    paths=allpaths(b,paths)
  return paths

def solve(a):
  ipos=list(zip(*(a==1).nonzero()))
  fpos=list(zip(*(a==2).nonzero()))[0]
  paths=[ipos]
  paths=allpaths(a,paths)
  M=a.shape[0]*a.shape[1]
  minlen=M
  for path in paths:
    if path[-1] in [FINAL]:
      minlen=min(minlen,len(path)-1)
  if minlen==M: return None
  else: return minlen

n,m=5,6
a=init(n,m)
print(n,m)
print(a)

minlen=solve(a)
print(minlen)