网站正在建设 下载,域名是什么样式的,上海建设工程咨询网站,wordpress选择windows还是题目描述
小张冒充 X 星球的骑士#xff0c;进入了一个奇怪的城堡。
城堡里边什么都没有#xff0c;只有方形石头铺成的地面。
假设城堡地面是 nn 个方格。如下图所示。 按习俗#xff0c;骑士要从西北角走到东南角。可以横向或纵向移动#xff0c;但不能斜着走#xf…题目描述
小张冒充 X 星球的骑士进入了一个奇怪的城堡。
城堡里边什么都没有只有方形石头铺成的地面。
假设城堡地面是 n×n 个方格。如下图所示。 按习俗骑士要从西北角走到东南角。可以横向或纵向移动但不能斜着走也不能跳跃。每走到一个新方格就要向正北方和正西方各射一箭。城堡的西墙和北墙内各有 n 个靶子同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目你能推断出骑士的行走路线吗有时是可以的比如上图中的例子。
本题的要求就是已知箭靶数字求骑士的行走路径测试数据保证路径唯一
输入描述
第一行一个整数 N (0≤N≤20)表示地面有 N×N 个方格。
第二行 N 个整数空格分开表示北边的箭靶上的数字自西向东
第三行 N 个整数空格分开表示西边的箭靶上的数字自北向南
输出描述
输出一行若干个整数表示骑士路径。
为了方便表示我们约定每个小格子用一个数字代表从西北角开始编号: 0,1,2,3 ⋯⋯
比如上图中的方块编号为
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入输出样例
示例 输入 4
2 4 3 4
4 3 3 3输出 0 4 5 1 2 3 7 11 10 9 13 14 15
思路 DFS题目要求输出一条路径用DFS很合适DFS搜索过程中自然生成一条路径。 剪枝每走到一个格子对应的靶子上箭多一支靶子上的箭等于给定的数字后就不用再DFS下去了。或者做减法靶子的数字减到0) 记录路径的技巧:根据题目的要求用栈来跟踪DFS的过程记录DFS走过的路径是最方便的。DFS到某个格子时把这个格子放到栈里表示路径增加了这个格子。DFS回溯的时候退出了这个格子表示路径上不再包括这个格子需要从栈中弹走这个格子。
参考代码
def dfs(x,y):if a[x]0 or b[y]0:#先开头检验是否符合标准returnif xn-1 and yn-1:#走到终点flag1for i in range(n): #检查每个箭靶上的数字是否减尽if a[i]!0 or b[i]!0:flag0returnif flag1:for i in range(len(path)):print(path[i],end )l[(1,0),(-1,0),(0,-1),(0,1)] for i in range(4):xtxl[i][0]ytyl[i][1]if 0xtn and 0ytn and vis[xt][yt]0:vis[xt][yt]1 #标记现场path.append(xt*nyt) #这个是坐标的计算方法a[xt]-1; b[yt]-1dfs(xt,yt) path.pop() a[xt]1; b[yt]1 #还原现场vis[xt][yt]0nint(input())
vis[[0]*n for i in range(n)]
path[]
path.append(0)
blist(map(int,input().split()))
alist(map(int,input().split()))
vis[0][0]1
a[0]-1; b[0]-1
dfs(0,0)
