按习俗#xff0c;骑士要从西北角走到东南角。

可以横向或纵向移动#xff0c;但不能斜着走#xf…题目描述

小张冒充

按习俗骑士要从西北角走到东南角。

可以横向或纵向移动但不能斜着走也不能跳跃。

每走到一个新方格就要向正北方和正西方各射一箭。

城堡的西墙和北墙内各有

个靶子同一个方格只允许经过一次。

但不必走完所有的方格。

如果只给出靶子上箭的数目你能推断出骑士的行走路线吗有时是可以的比如上图中的例子。

本题的要求就是已知箭靶数字求骑士的行走路径测试数据保证路径唯一

输入描述

为了方便表示我们约定每个小格子用一个数字代表从西北角开始编号:

0,1,2,3

DFS题目要求输出一条路径用DFS很合适DFS搜索过程中自然生成一条路径。

剪枝每走到一个格子对应的靶子上箭多一支靶子上的箭等于给定的数字后就不用再DFS下去了。

或者做减法靶子的数字减到0)

记录路径的技巧:根据题目的要求用栈来跟踪DFS的过程记录DFS走过的路径是最方便的。

DFS到某个格子时把这个格子放到栈里表示路径增加了这个格子。

DFS回溯的时候退出了这个格子表示路径上不再包括这个格子需要从栈中弹走这个格子。

参考代码

range(len(path)):print(path[i],end

for

range(4):xtxl[i][0]ytyl[i][1]if

0xtn

blist(map(int,input().split()))

alist(map(int,input().split()))

vis[0][0]1