ZOJ - 3861 Valid Pattern Lock 【全排列】

题目链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3861

思路

先生成全排列，然后判断哪些情况不符合的，剔除就好了

代码中 init（） 部分 就是 先指明 哪两个数字之间 是必须有另外一个数字的

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1);

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 2e5 + 5;

const int MOD = 1e9 + 7;

int n;

int c[10][10];

int vis[10];

bool judge(vector <int> ans)

{

    for (int i = 0; i < n - 1; i++)

    {

        if (c[ans[i]][ans[i + 1]] && vis[c[ans[i]][ans[i + 1]]] == 0)

            return false;

        vis[ans[i]] = 1;

    }

    return true;

}

void init()

{

    CLR(c);

    c[1][3] = 2, c[3][1] = 2;

    c[1][7] = 4, c[7][1] = 4;

    c[1][9] = 5, c[9][1] = 5;

    c[2][8] = 5, c[8][2] = 5;

    c[3][9] = 6, c[9][3] = 6;

    c[3][7] = 5, c[7][3] = 5;

    c[4][6] = 5, c[6][4] = 5;

    c[7][9] = 8, c[9][7] = 8;

}

int main()

{

    init();

    int t;

    cin >> t;

    while (t--)

    {

        scanf("%d", &n);

        vector <int> pre;

        int num;

        for (int i = 0; i < n; i++)

        {

            scanf("%d", &num);

            pre.pb(num);

        }

        sort(pre.begin(), pre.end());

        vector < vector <int> > ans;

        do

        {

            CLR(vis);

            if (judge(pre))

                ans.pb(pre);

        } while (next_permutation(pre.begin(), pre.end()));

        int len = ans.size();

        printf("%d\n", len);

        for (int i = 0; i < len; i++)

        {

            for (int j = 0; j < n; j++)

            {

                if (j)

                    printf(" ");

                printf("%d", ans[i][j]);

            }

            printf("\n");

        }

    }

}