hihoCoder#1054 滑动解锁

原题地址

回溯搜索

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

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

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

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

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

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

代码：

 #include <iostream>

 #include <cstring>

 using namespace std;

 int impossible[];

 bool integrity_check(int piece[][], int path[][]) {

   for (int i = ; i < ; i++)

     for (int j = ; j < ; j++)

         if (piece[i][j] && !path[i][j])

           return false;

   return true;

 }

 bool degree_check(int piece[][], int path[][], int b, int e) {

   if (piece[b][e])

     return true;

   int bdegree = ;

   int edegree = ;

   for (int i = ; i < ; i++) {

     bdegree += path[b][i] || piece[b][i] ?  : ;

     edegree += path[e][i] || piece[e][i] ?  : ;

   }

   return bdegree <  && edegree < ;

 }

 bool collineation_check(int visited[], int b, int e) {

   int t = (b + ) *  + e + ;

   return impossible[t] <  || visited[impossible[t] - ];

 }

 bool check(int piece[][], int path[][], int visited[], int b, int e) {

   if (visited[e])

     return false;

   return degree_check(piece, path, b, e) && collineation_check(visited, b, e);

 }

 int search(int piece[][], int path[][], int visited[], int p, int len) {

   int res = ;

   if (len >=  && integrity_check(piece, path))

     res++;

   for (int i = ; i <  && len < ; i++) {

     if (check(piece, path, visited, p, i)) {

       visited[i] = ;

       path[p][i] = path[i][p] = ;

       res += search(piece, path, visited, i, len + );

       path[p][i] = path[i][p] = ;

       visited[i] = ;

     }

   }

   return res;

 }

 int main() {

   int T;

   memset(impossible, -, sizeof(int) * );

   impossible[] = ;

   impossible[] = ;

   impossible[] = ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   impossible[]= ;

   cin >> T;

   while (T--) {

     int N;

     int piece[][] = {{, }};

     int path[][] = {{, }};

     int visited[] = {};

     int res = ;

     cin >> N;

     for (int i = ; i < N; i++) {

       int a, b;

       cin >> a >> b;

       piece[a - ][b - ] = piece[b - ][a - ] = ;

     }

     for (int i = ; i < ; i++) {

       visited[i] = ;

       res += search(piece, path, visited, i, );

       visited[i] = ;

     }

     cout << res << endl;

   }

   return ;

 }

巴特西

hihoCoder#1054 滑动解锁

最新文章

热门文章