given a grid of paths with different width, how can i find a path which leads to the end point?
The path is going to be represented by a two dimentional array where 0 means cannot be walk on, 1 means it is walkable, 2 represents starting point and 3 represents end point. Consider the following example:
21111111100000
00000011000000
00001111111111
00001111100111
00001110000101
00001111100113
in the above example the width of a path varies from 1 to 3, and there exists many solutions which would lead to the end point. I want to find one path which leads to it and the path does not have to be the shortest one (should not be the longest one either). The width of each path is unknown which means the grid could be all "1"s except the starting and end point.
Edited: The path should not contain uneccessary "wasted" walk meaning that if a vertical path has width 2 the result should not just walk down the path and then take one step right then walk all the way up
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)
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***