题目描述
小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一
个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4×4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着
字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将
玩具蛇放进去。
算法(暴力搜索)
枚举格子中的每两个点,其中一个作为起点,另外一个作为终点,记录终点到起点走过的步数
代码
#include<iostream>
#include<algorithm>
using namespace std;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int ans;
bool st[4][4];
void dfs(int x, int y, int ex, int ey, int cnt){
if(x == ex && y == ey){
if(cnt == 16) ans ++;//起点到终点的路径上有没有16个点
return ;
}
st[x][y] = true;//将每个走过的点标记
for(int i = 0; i < 4; i ++){
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= 4 || b < 0 || b >= 4) continue;
if(st[a][b]) continue;
dfs(a, b, ex, ey, cnt + 1);
}
st[x][y] = false;//恢复现场
}
int main(){
for(int i = 0; i < 4; i ++)
for(int j = 0; j < 4; j ++)
for(int x = 0; x < 4; x ++)
for(int y = 0; y < 4; y ++)
dfs(i, j, x, y, 1);
cout << ans << endl;
return 0;
}