玩具蛇。。

12.玩具蛇 - 蓝桥云课 (lanqiao.cn)
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可
小蓝有一条玩具蛇，一共有16节，上面标着数字1至16每一节都是一个正方形的形状。相邻的两节可以成直线或者成90度角
小蓝还有一个4x4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到P共16个字母
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
下图给出了两种方案

import os
import sys

# 请在此输入您的代码
def fc():
  M,N=4,4
  W=16  #16节
  ans=0
  direction=[(1,0),(-1,0),(0,1),(0,-1)]
  flag=[[0]*N for _ in range(M)]

  def dfs(x,y,k):
    nonlocal ans
    if k ==W: #16节放好了,返回答案
      ans+=1
      return
    for d in direction:
      if 0<=x+d[0]<M and 0<=y+d[1]<N and flag[x+d[0]][y+d[1]] == 0: #没有超出界限且没有被搜索过
        flag[x][y] =1
        dfs(x+d[0],y+d[1],k+1) #搜索下一节
        flag[x][y]=0 #通过将 flag[x][y] 重置为未访问，我们可以确保在下一次搜索到该位置时，它将被重新考虑，并有机会被包含在另一个路径中
    
  for i in range(M):
    for j in range(N):
      dfs(i,j,1)
  return ans
print(fc())