描述

滑動解鎖是智能手機一項常用的功能。你需要在3x3的點陣上，從任意一個點開始，反復移動到一個尚未經過的"相鄰"的點。這些劃過的點所組成的有向折線，如果與預設的折線在圖案、方向上都一致，那么手機將解鎖。兩個點相鄰當且僅當以這兩個點為端點的線段上不存在尚未經過的點。此外，這條折線還需要至少經過4個點。

為了描述方便，我們給這9個點從上到下、從左到右依次編號1-9。那么1->2->3是不合法的，因為長度不足。1->3->2->4也是合不法的，因為1->3穿過了尚未經過的點2。2->4->1->3->6是合法的，因為1->3時點2已經被劃過了。

作為一個愛逛知乎的好少年，小Hi已經知道一共有389112種不同的解鎖方案。不過小Hi不滿足于此，他希望知道，當已經瞥視到一部分折線的情況下，有多少種不同的方案。

遺憾的是，小Hi看到的部分折線既不一定是連續的，也不知道方向。例如看到1-2-3和4-5-6，那么1->2->3->4->5->6，1->2->3->6->5->4, 3->2->1->6->5->4->8->9等都是合法的方案。

輸入

第一行包含一個整數T(1 <= T <= 10)，代表測試數據組數。

每個測試數據第一行是一個整數N(0 <= N <= 8)，代表小Hi看到的折線段數目。

以下N行每行包含兩個整數X, Y (1 <= X, Y <= 9)，代表小Hi看到點X和點Y是直接相連的。

輸出

對于每組數據輸出合法的方案數目。

樣例輸入

3 0 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 4 2 4 2 5 8 5 8 6

樣例輸出

389112 2 258

---

方法是利用深度優先搜索嘗試所有可能，并累計符合的方案數，感覺效率很低啊，難道題目就是這樣的意圖? 1 #include<stdio.h> 2 #include<iostream> 3 #include<cstring> 4 5 using namespace std; 6 7 int test[10][10],vis[10],depth,aim_depth,n,res,es[10][10]; 8 9 10 int valid(int x,int y) 11 { 12 if((test[x][y]||test[y][x])&&!vis[(x+y)/2]) 13 { 14 return 0; 15 } 16 return 1; 17 } 18 19 void dfs(int x,int depth,int e) 20 { 21 vis[x]=1; 22 if(depth==aim_depth&&e==n) 23 { 24 ++res; 25 return; 26 } 27 28 for(int i=1;i<10;++i) 29 { 30 if(!vis[i]) 31 { 32 if(!valid(x,i)) 33 { 34 continue; 35 } 36 if(es[x][i]) 37 { 38 dfs(i,depth+1,e+1); 39 } 40 else 41 { 42 dfs(i,depth+1,e); 43 } 44 vis[i]=0; 45 } 46 } 47 } 48 49 int main() 50 { 51 memset(test,0,sizeof(test)); 52 test[1][3]=test[3][1]=test[1][7]=test[7][1]=1; 53 test[2][8]=test[8][2]=test[4][6]=test[6][4]=1; 54 test[1][9]=test[9][1]=test[3][7]=test[7][3]=1; 55 test[9][3]=test[3][9]=test[9][7]=test[7][9]=1; 56 57 int k,m,i,j; 58 scanf("%d",&k); 59 for(i=1;i<=k;i++) 60 { 61 res=0; 62 memset(vis,0,sizeof(vis)); 63 memset(es,0,sizeof(es)); 64 65 cin>>n; 66 67 if(n==0) 68 { 69 cout<<389112<<endl; 70 continue; 71 } 72 73 for(j=0;j<n;++j) 74 { 75 int a,b; 76 cin>>a>>b; 77 es[a][b]=es[b][a]=1; 78 } 79 80 aim_depth=max(4,n+1); 81 82 for(;aim_depth<10;++aim_depth) 83 { 84 for(j=1;j<10;++j) 85 { 86 dfs(j,1,0); 87 vis[j]=0; 88 } 89 } 90 cout<<res<<endl; 91 92 } 93 return 0; 94 }

?

轉載于:https://www.cnblogs.com/Traveller-Leon/p/4843737.html

總結

以上是生活随笔為你收集整理的hihocoder#1054 : 滑动解锁（深度优先搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。