描述

滑動解鎖是智能手機一項常用的功能。你需要在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,1）代表1，（2,1）代表4 #include #include #include #include using namespace std;int n;//看到的折線段個數 int num; int len;//折線長度 int cnt;//方案總數 bool visited[4][4]; bool edege[10][10];bool canReach(int i1, int j1, int i2, int j2) {if(abs(i1 - i2) > 1){if(abs(j1 - j2) > 1 || j1 == j2)return visited[(i1 + i2) / 2][(j1 + j2) / 2];elsereturn true;}else if(abs(j1 - j2) > 1){if(i1 == i2)return visited[i1][(j1 + j2) / 2];elsereturn true;}return true; }void dfs(int ii, int jj) {visited[ii][jj] = true;len++;if(len > 3 && num == n)cnt++;for(int i = 1; i < 4; i++){for(int j = 1; j < 4; j++){if(!visited[i][j] && canReach(ii, jj, i, j)){bool flag = edege[3*ii + jj - 3][3*i + j - 3];if(flag){num++;}dfs(i , j);if(flag)num--;}}}visited[ii][jj] = false;len--; }int main() {int t, i, j, x, y;cin>>t;while(t--){cnt = 0;cin>>n;memset(edege, false, sizeof(edege));for(i = 0; i < n; i++){cin>>x>>y;edege[x][y] = edege[y][x] = true;}for(i = 1; i < 4; i++){for(j = 1; j < 4; j++){len = num = 0;memset(visited, false, sizeof(visited));dfs(i , j);}}cout<<

總結

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

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