擅长:python、mysql、java
<p>你可以用一个简单的<a href="https://en.wikipedia.org/wiki/Breadth-first_search" rel="nofollow noreferrer">breadth first search</a>来完成这个。基本上,网格中的每个单元格都对应于图中的一个节点,相邻单元格之间有边。从起始位置开始,不断扩展可通过的单元格,直到找到目标单元格。</p>
<pre><code>def bfs(grid, start):
queue = collections.deque([[start]])
seen = set([start])
while queue:
path = queue.popleft()
x, y = path[-1]
if grid[y][x] == goal:
return path
for x2, y2 in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
if 0 <= x2 < width and 0 <= y2 < height and grid[y2][x2] != wall and (x2, y2) not in seen:
queue.append(path + [(x2, y2)])
seen.add((x2, y2))
</code></pre>
<p>网格设置和结果:(请注意,我使用的是符号而不是数字,原因是这样更容易直观地分析网格并验证解决方案。)</p>
<pre><code>wall, clear, goal = "#", ".", "*"
width, height = 10, 5
grid = ["..........",
"..*#...##.",
"..##...#*.",
".....###..",
"......*..."]
path = bfs(grid, (5, 2))
# [(5, 2), (4, 2), (4, 3), (4, 4), (5, 4), (6, 4)]
</code></pre>