14
14
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 2
0

所有题解在洛谷 IDE 中得到的测试结果为全部超时。

应该在每一次选择之前对于当前位置的可选骨牌去重。

不然对于大量的合法但是最后差一点点的情况的复杂度为合法部分的全排列。

参考代码。

#include <cstdio>
#include <cstdlib>
#include <map>
#include <tuple>
#include <utility>
constexpr int MaxN = 2e1 + 5;
int n, m;
int end;
int a[MaxN];
int b[MaxN];
int pre[MaxN];
bool vis[MaxN];
bool dfs(int u)
{
    if (u > n)
    {
        return pre[n] == end;
    }
    std::map<std::tuple<int, int>, bool> use;
    for (int i = 1; i <= m; i++)
    {
        if (vis[i])
        {
            continue;
        }
        if (b[i] == pre[u - 1])
        {
            std::swap(a[i], b[i]);
        }
        if (use[{a[i], b[i]}])
        {
            continue;
        }
        use[{a[i], b[i]}] = true;
        if (a[i] == pre[u - 1])
        {
            pre[u] = b[i];
            vis[i] = true;
            if (dfs(u + 1))
            {
                return true;
            }
            vis[i] = false;
        }
    }
    return false;
}
void solve()
{
    scanf("%d", &n);
    if (n == 0)
    {
        exit(0);
    }
    scanf("%d", &m);
    scanf("%*d%d", &pre[0]);
    scanf("%d%*d", &end);
    for (int i = 1; i <= m; i++)
    {
        vis[i] = false;
        scanf("%d%d", &a[i], &b[i]);
    }
    printf("%s\n", dfs(1) ? "YES" : "NO");
}
int main()
{
    for (;;)
    {
        solve();
    }
    return 0;
}