2020第十一届蓝桥杯国赛C/C++b组 玩具蛇（DFS)

【问题描述】
小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将玩具蛇放进去。

题解

尝试令每一个位置作为一个入口，也就是起点。

然后每次尝试向周围遍历，这样的话，有可能出现走不动的情况

即还没到16，周围已经没堵死了。所以只需要记录到16的情况。

反思：

一开始我用bfs，发现不怎么行，这个一看就算bfs。

所以换了dfs，一开始想的是遍历1-16，每次。仔细想了一下不行。然后想到这个

可是仍不对，从网上搜了代码，真巧了，他和我的写法一样。我还以为我的写法根本不对。

原来是：入口的时候，没加dp[i][j] = 1;和dp[i][j] = 0;

还有个地方写错i了

Code

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
struct node
{
    int x, y, d;
    bool dp[20][20];
};
bool dp[20][20];
long long cnt;
void dfs(int i, int j, int x)
{
    if (x == 16)
    {
        cnt++;
        return;
    }

    for (int k = 0; k < 4; k++)
    {
        int nx = dx[k] + i;
        int ny = dy[k] + j;
        if (nx >= 0 && ny >= 0 && nx < 4 && ny < 4 && !dp[nx][ny])
        {
            dp[nx][ny] = 1;
            dfs(nx, ny, x + 1);
            dp[nx][ny] = 0;
        }
    }
}
int main()
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            dp[i][j] = 1;
            dfs(i, j, 1);
            dp[i][j] = 0;
        }
    }
    cout << cnt;
    return 0;
}