问题描述

小蓝有一条玩具蛇，一共有16节，上面标着数字1至16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成90 度角。

小蓝还有一个4×4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到P共16个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

类似于第八届蓝桥杯省赛C++ B组方格分割那道题，用DFS解决。

答案

552

代码

#include <iostream>using namespace std;const int n=4;int ans=0;int visit[n][n];   //4*4的格子int dir[4][2]={0,1,0,-1,1,0,-1,0};  //方向，右左下上//核心dfs算法void dfs(int x,int y,int index){if(index18477== 15){   //16个格子走完后，即为一种摆放方法ans++;return;}for(int k=0;k<4;k++){int tx=x+dir[k][0];int ty=y+dir[k][1];if(tx<0 || tx>3 || ty<0 || ty>3)  //判断出界continue;if(visit[tx][ty])  //格子已经走过continue;     //continue是结束这个循环，开始下一个循环visit[tx][ty]=1;dfs(tx,ty,index+1);visit[tx][ty]=0;}}int main(){//16个格子都可以作为dfs的起始位置，因为只要玩具蛇有一节位置不一样，就可以算作两种方案for(int i=0;i<4;i++){for(int j=0;j<4;j++){visit[i][j]=1;dfs(i,j,0);visit[i][j]=0;}}cout<<ans<<endl;return 0;}

之前自己写的时候结果算出了六百多，后来发现是dfs()里的边界逻辑有误，一开始是这样写的

for(int k=0;k<4;k++){if(x<0 || x>3 || y<0 || y>3)continue;int tx=x+dir[k][0];int ty=y+dir[k][1];if(visit[tx][ty])  //格子已经走过continue;     //continue是结束这个循环，开始下一个循环visit[tx][ty]=1;dfs(tx,ty,index+1);visit[tx][ty]=0;}

直接用了x和y来判断边界，但是顺序错了，没注意后面还会再移动一格，有可能就出界了。或者把判断出界放在if(index == 15)那里也可以。