题面
【问题描述】
小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一 个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着 字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。
下图给出了两种方案：
请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩 具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路
DFS，从盒子的每个位置开始放，深度优先搜索，注意控制边界条件，递归16层即为一种合法方案，计数器加一。
答案：552
代码
#include<iostream>
#include<cstring>
using namespace std;
int res = 0, dir[4][2] = {{0, 1},
{1, 0},
{0, -1},
{-1, 0}};
int g[5][5];
void dfs(int i, int j, int k) {
if (k == 17) {
res++;
return;
}
for (int d = 0; d < 4; d++) {
int ti = i + dir[d][0], tj = j + dir[d][1];
if (ti < 1 || ti > 4 || tj < 1 || tj > 4) continue;
if (g[ti][tj]) continue;
g[ti][tj] = k;
dfs(ti, tj, k + 1);
g[ti][tj] = 0;
}
}
int main() {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
g[i][j] = 1;
dfs(i, j, 2);
memset(g, 0, sizeof(g));
}
}
cout << res << endl;
return 0;
}
| 标题： | 2020第十一届蓝桥杯国赛-E玩具蛇 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/108 |
| 更新： | 2022-09-18 22:39:30 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |