捕获.PNG

感觉这个题应该很简单的，但是我没做出来！，真的菜

笔试没做出来的写法！

#测试数据
#2,2 0,0 2,2 3 0,1 0,2 1,1
steps=[]
g=[]
g_col,g_row=0,0
end_pos=[]

def trace(x,y):
    global g,g_col,g_row,steps,end_pos
    if x==end_pos[0] and y==end_pos[1]:
        steps.append([x,y])
        print(steps)
        return
    else:
        if g[x][y]==0:
            steps.append([x,y])
            print(steps)
            g[x][y]=1
            if x!=0:
                print('up')
                trace(x-1,y)
            elif x!=g_row:
                print('down')
                trace(x+1,y)
            elif y!=0:
                print('left')
                trace(x,y-1)
            elif y!=g_col:
                print('right')
                trace(x,y+1)
            else:
                print('no way out')
            
    
s=input().split()
graph,start,end=s[0].split(','),s[1].split(','),s[2].split(',')
x_num=int(s[3])
x_points=[]
for i in range(x_num):
    x_point=[0]*2
    x_str=s[4+i].split(',')
    x_point[0]=int(x_str[0])
    x_point[1]=int(x_str[1])
    x_points.append(x_point)
g_row,g_col=int(graph[0]),int(graph[1])
start_pos=int(start[0]),int(start[1])
end_pos=int(end[0]),int(end[1])
g=[[0]*(g_col+1) for i in range(g_row+1)]

for x_point in x_points:
    g[x_point[0]][x_point[1]]=1
print(g)
trace(start_pos[0],start_pos[1])

笔试后想出来的写法

steps=[]
g=[]
g_col,g_row=0,0
end_pos=[]
nextstep=[[-1,0],[1,0],[0,-1],[0,1]]
def trace(x,y):
    global g,g_col,g_row,steps,end_pos
    if x==end_pos[0] and y==end_pos[1]:
        steps.append([x,y])
        print(steps)
        return
    else:
        for i in range(4):
            tx,ty=(x+nextstep[i][0]),(y+nextstep[i][1])
            if tx<0 or tx>g_row or ty<0 or ty>g_col or g[tx][ty]==1:
                continue
            else:
                steps.append([tx,ty])
                #print(steps)
                g[tx][ty]=1
                trace(tx,ty)
                steps.pop()
                g[tx][ty]=0

s=input().split()
graph,start,end=s[0].split(','),s[1].split(','),s[2].split(',')
x_num=int(s[3])
x_points=[]
for i in range(x_num):
    x_point=[0]*2
    x_str=s[4+i].split(',')
    x_point[0]=int(x_str[0])
    x_point[1]=int(x_str[1])
    x_points.append(x_point)
g_row,g_col=int(graph[0]),int(graph[1])
start_pos=int(start[0]),int(start[1])
end_pos=int(end[0]),int(end[1])
g=[[0]*(g_col+1) for i in range(g_row+1)]

for x_point in x_points:
    g[x_point[0]][x_point[1]]=1
g[start_pos[0]][start_pos[1]]=1
steps.append([0,0])
trace(start_pos[0],start_pos[1])

1，为什么上面那种不行？
确实进行了遍历，但是一旦踩到障碍物就结束了（if g[x][y]==1)直接让遍历不走下面的路了
相当于对当前进行了约束，但是没有对下一步是否会走障碍物进行约束，一旦走入障碍物，就无法再进入遍历流程
2，为什么下面行？
回溯法有点像深度优先遍历，但是没有搜索完所有的可能性
1 第一个if是整体的返回条件，是遍历到第一个可能结果就返回
2 for循环代表对四个分支的遍历
3 第二个if代表当前遍历的分支已经不满足基本要求的条件限制时，进行剪枝，跳过当前分支
3，总结
回溯法就要对下一步进行试错判断，判断下一步能不能走，不能走剪枝，走能走的路