fork download
copy 
  1. #include <stdio.h>
  2. #include <time.h>
  3. // #define FILE_TEST
  4. #define max(a, b) (((a) > (b)) ? (a) : (b))
  5. #define min(a, b) (((a) < (b)) ? (a) : (b))
  6. #define INF 13
  7. int T, n, n_sqr;
  8. int a[110][110];
  9. int idx(int i, int j, int k) { return (i - 1) * n_sqr + (j - 1) * n + (k - 1); }
  10. int real_idx(int _i, int _j, int _k) 
  11. {
  12.     int i = min(_i, min(_j, _k)), k = max(_i, max(_j, _k)), j = _i ^ _j ^ _k ^ i ^ k; 
  13.     return (i - 1) * n_sqr + (j - 1) * n + (k - 1); 
  14. }
  15. int cnt(int i, int j, int k) { return a[i][j] + a[j][k] + a[i][k]; }
  16. int vec[1000010], pos[1000010], sz;
  17. void _insert(int x) { vec[++sz] = x, pos[x] = sz; }
  18. void _remove(int x) { pos[vec[sz]] = pos[x], vec[pos[x]] = vec[sz], vec[sz--] = 0; }
  19. char empty() { return !sz; }
  20. void clear() 
  21. {
  22.     for (int i = 1; i <= sz; ++i)
  23.         pos[vec[i]] = 0, vec[i] = 0;
  24.     sz = 0; 
  25. }
  26. int global_ans;
  27. void change(int _i, int _j)
  28. {
  29.     int off = (a[_i][_j] == 1) ? 1 : -1;
  30.     for (int _k = 1; _k <= n; ++_k)
  31.         if ((_k ^ _i) && (_k ^ _j) && cnt(_i, _j, _k) == 2)
  32.             _remove(real_idx(_i, _j, _k));
  33.     a[_i][_j] = a[_j][_i] = a[_i][_j] ^ 1;
  34.     for (int _k = 1; _k <= n; ++_k)
  35.         if ((_k ^ _i) && (_k ^ _j) && cnt(_i, _j, _k) == 2)
  36.             _insert(real_idx(_i, _j, _k));    
  37. }
  38. void dfs(int cur)
  39. {
  40.     if (empty())
  41.     {
  42.         global_ans = cur - 1;
  43.         return;
  44.     }
  45.     if (cur >= global_ans)
  46.         return; 
  47.     int sta = vec[1];
  48.     int i = sta / n_sqr + 1, j = ((sta / n) % n) + 1, k = sta % n + 1;
  49.     change(i, j), dfs(cur + 1), change(i, j);
  50.     change(j, k), dfs(cur + 1), change(j, k);
  51.     change(i, k), dfs(cur + 1), change(i, k);
  52. }
  53.  
  54. int main()
  55. {
  56. #ifdef FILE_TEST  
  57.     freopen("in.txt", "r", stdin);
  58.     clock_t start, finish;
  59.     start = clock();
  60. #endif
  61.     scanf("%d", &T);
  62.     for (int t = 1; t <= T; ++t)
  63.     {
  64.         clear();
  65.         scanf("%d", &n), n_sqr = n * n;
  66.         global_ans = INF;
  67.         for (int i = 1; i <= n; ++i)
  68.             for (int j = 1; j <= n; ++j)
  69.                 scanf("%d", &a[i][j]);
  70.         for (int i = 1; i <= n; ++i)
  71.             for (int j = i + 1; j <= n; ++j)
  72.                 for (int k = j + 1; k <= n; ++k)
  73.                     if (cnt(i, j, k) == 2)
  74.                         _insert(idx(i, j, k));
  75.  
  76.         dfs(1);
  77.         printf("%d\n", global_ans == INF ? -1 : global_ans);
  78.         // printf("Case #%d: %d\n", t, global_ans == INF ? -1 : global_ans);
  79.     }
  80. #ifdef FILE_TEST   
  81.     finish = clock();
  82.     fprintf(stderr, "time : %.3f s\n", ((double)(finish - start)) / CLOCKS_PER_SEC);
  83. #endif
  84. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
7
7
1 0 0 0 0 0 0
0 1 1 1 0 0 0
0 1 1 0 0 0 1
0 1 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 1 0 0 0 1
8
1 1 1 0 0 0 1 1
1 1 1 0 0 0 0 1
1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
8
1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 1 0 0 0 0 0 1
3
1 0 0
0 1 0
0 0 1
7
1 1 0 0 0 1 0
1 1 0 0 1 0 1
0 0 1 1 0 0 1
0 0 1 1 0 0 0
0 1 0 0 1 0 0
1 0 0 0 0 1 1
0 1 1 0 0 1 1
6
1 1 1 0 0 0
1 1 1 0 1 1
1 1 1 0 0 0
0 0 0 1 0 0
0 1 0 0 1 1
0 1 0 0 1 1
5
1 1 1 1 1
1 1 1 1 0
1 1 1 0 1
1 1 0 1 1
1 0 1 1 1
stdout
copy 
2
4
1
0
4
2
2
https://ideone.com/W1eNGt
language:
C (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!