试题 E: 玩具蛇 本题总分：15 分
【问题描述】
小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一
个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着
字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将
玩具蛇放进去。
下图给出了两种方案：
文章图片
【蓝桥杯|蓝桥python——玩具蛇】请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩
具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分！
文章图片
以上是我的思路，然后关于DFS的话递归过程有几个变量，就设几个参数
代码如下
def dfs(i,j,step):
global count,isVisited
if step>16:#大于16，则剪枝
return
if step==16 :#若刚好等于16，则找到一种方案
count+=1
return
for k in range(4):#生成（i，j）所有邻居
ii=i+d[k][0]
jj=j+d[k][1]
if ii>=0 and ii<=3 and jj>=0 and jj<=3 and isVisited[ii][jj]==False:#如符合条件且未被访问
isVisited[ii][jj]=True
dfs(ii,jj,step+1)
isVisited[ii][jj]=False#回溯：作用是一个点可由多个父节点count=0
d=[(-1,0),(1,0),(0,1),(0,-1)]#四个方向
for i in range(4):
for j in range(4):#其中（i，j）指玩具蛇头即1所在的位置
isVisited=[[False for _ in range(4)] for _ in range(4) ]#将所有点都置为未访问
isVisited[i][j]=True#蛇头1已访问
dfs(i,j,1)print(count)答案：552
推荐阅读
- 蓝桥杯|蓝桥python——方格分割【2017 第四题】
- CTF|2021DASCTF八月挑战赛Writeup
- 蓝桥杯|蓝桥python—— 剪邮票【2016 第七题】
- mybatis框架的使用|mybatis中使用缓存、懒加载、事务
- 程序员|java写入mysql数据库乱码，涨姿势了！
- 备战蓝桥杯|【蓝桥python冲刺17天】——如何轻松拿捏必考数论题（（第三弹））
- 备战蓝桥杯|【蓝桥python冲刺31天】——如何轻松拿捏必考数论题（（第一弹））
- #|python opencv 图像像素处理基础
- 神经网络|【论文导读】浅谈胶囊网络与动态路由算法