B2B hybris模块gen不起作用(B2B hybris module gen does not work)

 我同意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,'')
 
 一旦找到解决方案就使其停止的优化作为练习留给读者（你可以使洪水返回一个布尔值来指示它是否找到了什么，或使用全局标志）。 
 
 （ps我做了这个回答社区维基，因为我只是澄清了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***

I agree with Calumn: DFS is the simplest approach here. Here is a simple solution in python-like pseudocode. It will print the solution as a sequence of 'L','R',U','D' to indicate left,right,up, or down.
 
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,'')
 
The optimization of making it stop as soon as it finds a solution is left as an exercise to the reader (you could make flood return a boolean to indicate if it found something, or use a global flag).
 
(p.s. I made this answer community wiki since I'm just clarifying Calumn's answer. I can't claim much credit)
 
Breadth-First Search version, also in Python
 
For what it's worth, and just to show that breadth-first search is not that complicated, an actual runnable program in 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)
 
Output:
 
*******1100000
000000*1000000
000011******11
00001111100*11
00001110000*01
00001111100***