ZOJ3861:Valid Pattern Lock(DFS)

点击量:2

记录路径的题目,我是用been数组来保存当前选择的牌数,使用able表示能否选择,con表示中间的数字。奈何active point的设定是,必须存在这个点才能链接,例如1 3 1 3 9这组数据,因为2,5不存在所以不能连接 — 小坑,万万没想到。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define lln long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int con[10][10];
// 初始化不可达
void init()
{
    memset(con, 0, sizeof(con));
    for(int i = 1; i <= 4; i++)
    {
        con[i][10-i] = 5;
        con[10-i][i] = 5;
    }
    con[1][3] = con[3][1] = 2;
    con[1][7] = con[7][1] = 4;
    con[3][9] = con[9][3] = 6;
    con[7][9] = con[9][7] = 8;
}
int able[10];
int been[10];
int t; int n;
int res;
int seq[1000000][10];
void dfs(int num, int i)
{
    if(num == n+1)
    {
        for(int j = 1; j <= 9; j++)
            seq[res][been[j]] = j;
        res++;
    }
    else
        for(int j = 1; j <= 9; j++)
            // 凡是存在,并且中间没有阻碍点的均可
            if(able[j] == 1 && able[con[i][j]] == 1 && been[con[i][j]] != -1 && been[j] == -1)
            {
                been[j] = num;
                dfs(num+1, j);
                been[j] = -1;
            }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    cin >> t;
    init();
    int a[10];
    while(t--)
    {
        res = 0;
        memset(able, -1, sizeof(able)); // -1代表不可用
        memset(been, -1, sizeof(been)); // -1代表尚未到达,其他代表编号
        been[0] = 1;
        scanf("%d", &n);
        for(int i = 0; i< n; i++)
        {
            scanf("%d", &a[i]);
            able[a[i]] = 1; //能够使用
        }
        // 不可用的点可以通过
        for(int i = 1; i <= 9; i++)
            if(able[i] == -1) been[i] = 0;
        able[0] = 1;
        for(int i = 1; i <= 9; i++)
        {
            if(able[i] == 1)
            {
                been[i] = 1;
                dfs(2, i);
                been[i] = -1;
            }
        }
        printf("%d\n", res);
        int temp[10];
        for(int i = 0; i < res;i ++)
            for(int j = 1; j <= n; j++)
                printf("%d%c", seq[i][j], j == n ? '\n' : ' ');
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注