ZOJ 3861 Valid Pattern Lock-白红宇

ZOJ 3861 Valid Pattern Lock

阅读量：5113 次

发布时间：2019-06-13

本文共 1835 字，大约阅读时间需要 6 分钟。

题意：画图案所的问题，给出一个3 × 3拨号盘中的几个数字作为活跃点，问由活跃点能组合多少种解锁方式，并输出它们。一个合法的解锁方式包含以下几点：

一个方案中由一些点构成，每个点在按顺序触摸的时候都是第一次被触摸到，称这些点为活跃点。

如果在连接A，B两点的时候经过了另外的点，那么这个点必须出现在序列中，并且在A和B之前出现。

一个点被合法的线段多次通过是可以的，只要这个点在之前合法出现过。

解法：枚举排列，挨个判断是否合法，因为之前读错过题……所以写的比较啰嗦……正常应该不是很难写……就不介绍我的写法了……（捂脸

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;int n;int pass[10][10];void init(){ memset(pass, 0, sizeof(pass)); pass[1][3] = 2; pass[3][1] = 2; pass[1][7] = 4; pass[7][1] = 4; pass[3][9] = 6; pass[9][3] = 6; pass[7][9] = 8; pass[9][7] = 8; pass[2][8] = pass[3][7] = pass[1][9] = pass[4][6] = pass[8][2] = pass[7][3] = pass[9][1] = pass[6][4] = 5;}vector 
                   
                    
                      > res;bool judge(int a[10], int vis[10]){ int new_vis[10]; memcpy(new_vis, vis, sizeof(new_vis)); new_vis[a[0]] = false; for(int i = 1; i < n; i++) { if(!new_vis[a[i]]) return false; //cout << pass[a[i - 1]][a[i]] << endl; if(pass[a[i - 1]][a[i]] && new_vis[pass[a[i - 1]][a[i]]] == -1) return false; new_vis[pass[a[i - 1]][a[i]]] = 0; new_vis[a[i]] = 0; } return true;}int main(){ int T; while(~scanf("%d", &T)) { init(); while(T--) { res.clear(); scanf("%d", &n); int a[10]; int vis[10]; memset(vis, -1, sizeof(vis)); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); vis[a[i]] = 1; } sort(a, a + n); int ans = 0; do { if(judge(a, vis)) { ans++; vector 
                     
                       tmp; for(int i = 0; i < n; i++) tmp.push_back(a[i]); res.push_back(tmp); } }while(next_permutation(a, a + n));//枚举排列 printf("%d\n", ans); for(int i = 0; i < ans; i++) { for(int j = 0; j < n; j++) { if(j) printf(" "); printf("%d", res[i][j]); } puts(""); } } } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4433090.html

你可能感兴趣的文章