hihoCoder#1054 滑动解锁

原题地址

回溯搜索

对于每个待枚举的点，检查：

1. 度数检查：是否违反了出度入度限制。因为生成的路径除了首尾节点外，其他节点的出度和入度只能为2

2. 共线检查：是否违反了共线条件。即跨越了尚未枚举过的节点

对于枚举产生的路径，检查：

1. 长度检查：长度是否大于等于4

2. 完整性检查：是否包含了片段中出现的所有边

代码：

  1 #include <iostream>
  2 #include <cstring>
  3 
  4 using namespace std;
  5 
  6 int impossible[100];
  7 
  8 bool integrity_check(int piece[9][9], int path[9][9]) {
  9   for (int i = 0; i < 9; i++)
 10     for (int j = 0; j < 9; j++)
 11         if (piece[i][j] && !path[i][j])
 12           return false;
 13   return true;
 14 }
 15 
 16 bool degree_check(int piece[9][9], int path[9][9], int b, int e) {
 17   if (piece[b][e])
 18     return true;
 19 
 20   int bdegree = 0;
 21   int edegree = 0;
 22 
 23   for (int i = 0; i < 9; i++) {
 24     bdegree += path[b][i] || piece[b][i] ? 1 : 0;
 25     edegree += path[e][i] || piece[e][i] ? 1 : 0;
 26   }
 27 
 28   return bdegree < 2 && edegree < 2;
 29 }
 30 
 31 bool collineation_check(int visited[9], int b, int e) {
 32   int t = (b + 1) * 10 + e + 1;
 33   return impossible[t] < 0 || visited[impossible[t] - 1];
 34 }
 35 
 36 bool check(int piece[9][9], int path[9][9], int visited[9], int b, int e) {
 37   if (visited[e])
 38     return false;
 39 
 40   return degree_check(piece, path, b, e) && collineation_check(visited, b, e);
 41 }
 42 
 43 int search(int piece[9][9], int path[9][9], int visited[9], int p, int len) {
 44   int res = 0;
 45 
 46   if (len >= 4 && integrity_check(piece, path))
 47     res++;
 48 
 49   for (int i = 0; i < 9 && len < 9; i++) {
 50     if (check(piece, path, visited, p, i)) {
 51       visited[i] = 1;
 52       path[p][i] = path[i][p] = 1;
 53       res += search(piece, path, visited, i, len + 1);
 54       path[p][i] = path[i][p] = 0;
 55       visited[i] = 0;
 56     }
 57   }
 58 
 59   return res;
 60 }
 61 
 62 int main() {
 63   int T;
 64   memset(impossible, -1, sizeof(int) * 100);
 65   impossible[13] = 2;
 66   impossible[46] = 5;
 67   impossible[79] = 8;
 68   impossible[17]= 4;
 69   impossible[28]= 5;
 70   impossible[39]= 6;
 71   impossible[19]= 5;
 72   impossible[37]= 5;
 73   impossible[31]= 2;
 74   impossible[64]= 5;
 75   impossible[97]= 8;
 76   impossible[71]= 4;
 77   impossible[82]= 5;
 78   impossible[93]= 6;
 79   impossible[91]= 5;
 80   impossible[73]= 5;
 81 
 82   cin >> T;
 83   while (T--) {
 84     int N;
 85     int piece[9][9] = {{0, 0}};
 86     int path[9][9] = {{0, 0}};
 87     int visited[9] = {0};
 88     int res = 0;
 89 
 90     cin >> N;
 91     for (int i = 0; i < N; i++) {
 92       int a, b;
 93       cin >> a >> b;
 94       piece[a - 1][b - 1] = piece[b - 1][a - 1] = 1;
 95     }
 96 
 97     for (int i = 0; i < 9; i++) {
 98       visited[i] = 1;
 99       res += search(piece, path, visited, i, 1);
100       visited[i] = 0;
101     }
102 
103     cout << res << endl;
104   }
105   return 0;
106 }