fork download
copy 
  1. #include <stdio.h>
  2.  
  3. typedef unsigned int uint;
  4.  
  5. static void
  6. ban_hyouji (uint b)
  7. {
  8.     for (int i = 0; i < 25; i++) {
  9.         if (b & (1 << i))
  10.             printf (" x");
  11.         else
  12.             printf (" -");
  13.         if (i % 5 == 4)
  14.             printf ("\n");
  15.     }
  16.     printf ("\n");
  17. }
  18.  
  19. static uint
  20. r0 (uint b)
  21. {
  22.     return b;
  23. }
  24.  
  25. static uint
  26. r1 (uint b)
  27. {
  28.     uint t;
  29.  
  30.     t = ((b >> 3) & 0x00318c63) | ((b << 3) & 0x018c6318);
  31.     return ((t >> 1) & 0x0094a529) | ((t << 1) & 0x01294a52) | (b & 0x00421084);
  32. }
  33.  
  34. static uint
  35. r2 (uint b)
  36. {
  37.     uint t;
  38.  
  39.     t = ((b >> 15) & 0x000003ff) | ((b << 15) & 0x01ff8000);
  40.     return ((t >> 5) & 0x000f801f) | ((t << 5) & 0x01f003e0) | (b & 0x00007c00);
  41. }
  42.  
  43. static uint
  44. r3 (uint b)
  45. {
  46.     return r2 (r1 (b));
  47. }
  48.  
  49. static uint
  50. r4 (uint b)
  51. {
  52.     uint t;
  53.  
  54.     t = (((b << 12) ^ b) & 0x00318000);
  55.     b ^= (t | (t >> 12));
  56.     t = (((b << 8) ^ b) & 0x00400400);
  57.     b ^= (t | (t >> 8));
  58.     t = (((b << 4) ^ b) & 0x00920920);
  59.     b ^= (t | (t >> 4));
  60.  
  61.     return b;
  62. }
  63.  
  64. static uint
  65. r5 (uint b)
  66. {
  67.     return r1 (r4 (b));
  68. }
  69.  
  70. static uint
  71. r6 (uint b)
  72. {
  73.     return r2 (r4 (b));
  74. }
  75.  
  76. static uint
  77. r7 (uint b)
  78. {
  79.     return r3 (r4 (b));
  80. }
  81.  
  82. static int
  83. p0 (int c)
  84. {
  85.     return c;
  86. }
  87.  
  88. static int
  89. p1 (int c)
  90. {
  91.     return (c / 5) * 5 + 4 - c % 5;
  92. }
  93.  
  94. static int
  95. p2 (int c)
  96. {
  97.     return (4 - c / 5) * 5 + c % 5;
  98. }
  99.  
  100. static int
  101. p3 (int c)
  102. {
  103.     return 24 - c;
  104. }
  105.  
  106. static int
  107. p4 (int c)
  108. {
  109.     return c / 5 + (c % 5) * 5;
  110. }
  111.  
  112. static int
  113. p5 (int c)
  114. {
  115.     return 4 - c / 5 + (c % 5) * 5;
  116. }
  117.  
  118. static int
  119. p6 (int c)
  120. {
  121.     return c / 5 + (4 - c % 5) * 5;
  122. }
  123.  
  124. static int
  125. p7 (int c)
  126. {
  127.     return 4 - c / 5 + (4 - c % 5) * 5;
  128. }
  129.  
  130. static uint (*const ban_no_henkan[8]) (uint b) = {r0, r1, r2, r3, r4, r5, r6, r7};
  131. static uint (*const ban_wo_motoni_modosu[8]) (uint b) = {r0, r1, r2, r3, r4, r6, r5, r7};
  132. static int (*const masu_no_henkan[8]) (int c) = {p0, p1, p2, p3, p4, p5, p6, p7};
  133. static int (*const masu_wo_motoni_modosu[8]) (int c) = {p0, p1, p2, p3, p4, p6, p5, p7};
  134.  
  135. static int ikkasyo_ni_matomerareta_ima_iru_masu[12];
  136. static int ikkasyo_ni_matomerareta_hitotu_mae_no_masu[12];
  137.  
  138. static int ikkasyo_ni_matomerareta_genzai_iti_no_bangou[25][25];
  139. static int masu_wo_ikkasyo_ni_motteiku_tame_ni_hituyouna_henkan_bangou[25][25];
  140.  
  141. static void
  142. masu_wo_ikkasyo_ni_henkan_suru (int c, int f)
  143. {
  144.     int i, r;
  145.     uint b, m;
  146.     static uint bp[12][2];
  147.     static int n;
  148.  
  149.     b = (1 << c) | (1 << f);
  150.     for (r = 0, m = b, i = 1; i < 8; i++) {
  151.         if (ban_no_henkan[i] (b) < m) {
  152.             m = ban_no_henkan[i] (b);
  153.             r = i;
  154.         }
  155.     }
  156.     masu_wo_ikkasyo_ni_motteiku_tame_ni_hituyouna_henkan_bangou[c][f] = r;
  157.  
  158.     b = ban_no_henkan[r] (1 << c);
  159.     for (i = 0; i < n; i++) {
  160.         if (m == bp[i][0] && b == bp[i][1])
  161.             break;
  162.     }
  163.     ikkasyo_ni_matomerareta_genzai_iti_no_bangou[c][f] = i;
  164.  
  165.     if (i == n) {
  166.         bp[n][0] = m;
  167.         bp[n][1] = b;
  168.         ikkasyo_ni_matomerareta_ima_iru_masu[n] = masu_no_henkan[r] (c);
  169.         ikkasyo_ni_matomerareta_hitotu_mae_no_masu[n] = masu_no_henkan[r] (f);
  170.         n++;
  171.     }
  172. }
  173.  
  174. static int ugokeru_masu[25][25][4];
  175.  
  176. static void
  177. ugokeru_masu_wo_motomeru (int c, int f)
  178. {
  179.     int i = 0;
  180.  
  181.     if (c / 5 > 0 && c - 5 != f)
  182.         ugokeru_masu[c][f][i++] = c - 5;
  183.     if (c % 5 > 0 && c - 1 != f)
  184.         ugokeru_masu[c][f][i++] = c - 1;
  185.     if (c % 5 < 4 && c + 1 != f)
  186.         ugokeru_masu[c][f][i++] = c + 1;
  187.     if (c / 5 < 4 && c + 5 != f)
  188.         ugokeru_masu[c][f][i++] = c + 5;
  189.     ugokeru_masu[c][f][i] = -1;
  190. }
  191.  
  192. static uint
  193. idou_suru (uint b, int t)
  194. {
  195.     return b ^ (1 << t);
  196. }
  197.  
  198. unsigned char wr[12][33554432];
  199.  
  200. static void
  201. solve_0 ()
  202. {
  203.     int c, f, t, r, p;
  204.     uint b;
  205.     int i, j, k, l = 0, n;
  206.  
  207.     for (i = 0; i < 12; i++)
  208.         wr[i][0] = 1;
  209.     do {
  210.         n = 0;
  211.         printf ("%d\n", l++);
  212.         for (i = 0; i < 12; i++) {
  213.             c = ikkasyo_ni_matomerareta_ima_iru_masu[i];
  214.             f = ikkasyo_ni_matomerareta_hitotu_mae_no_masu[i];
  215.             for (j = 0; j < 33554432; j++) {
  216.                 if (wr[i][j])
  217.                     continue;
  218.                 wr[i][j] = 255;
  219.                 for (k = 0; k < 3; k++) {
  220.                     if ((t = ugokeru_masu[c][f][k]) < 0)
  221.                         break;
  222.                     p = ikkasyo_ni_matomerareta_genzai_iti_no_bangou[t][c];
  223.                     r = masu_wo_ikkasyo_ni_motteiku_tame_ni_hituyouna_henkan_bangou[t][c];
  224.                     b = ban_no_henkan[r] (idou_suru (j, t));
  225.                     if (wr[p][b] && wr[p][b] + 1 < wr[i][j])
  226.                         wr[i][j] = wr[p][b] + 1;
  227.                 }
  228.                 if (wr[i][j] < 255)
  229.                     n++;
  230.                 else
  231.                     wr[i][j] = 0;
  232.             }
  233.         }
  234.         printf ("%d\n", n);
  235.     } while (n);
  236. }
  237.  
  238. static void
  239. solve (uint b)
  240. {
  241.     int c, f, t, r, p;
  242.     uint o;
  243.     int i, k, l, m, n = 0;
  244.     int min;
  245.     int henkan_rireki[128];
  246.  
  247.     if (b == 0) {
  248.         ban_hyouji (b);
  249.         printf (" %d\n\n", n);
  250.         return;
  251.     }
  252.  
  253.     b ^= 0x00100000;
  254.     ban_hyouji (b ^ 0x00100000);
  255.     printf ("R");
  256.  
  257.     r = (wr[0][ban_no_henkan[2] (b)] < wr[0][ban_no_henkan[5] (b)]) ? 2 : 5;
  258.     henkan_rireki[n++] = r;
  259.     b = ban_no_henkan[r] (b);
  260.  
  261.     p = 0;
  262.     c = 1;
  263.     t = 0;
  264.     r = 0;
  265.  
  266.     while (b) {
  267.         f = masu_no_henkan[r] (c);
  268.         c = masu_no_henkan[r] (t);
  269.         min = 255;
  270.         m = -1;
  271.         for (k = 0; k < 3; k++) {
  272.             if ((t = ugokeru_masu[c][f][k]) < 0)
  273.                 break;
  274.             p = ikkasyo_ni_matomerareta_genzai_iti_no_bangou[t][c];
  275.             r = masu_wo_ikkasyo_ni_motteiku_tame_ni_hituyouna_henkan_bangou[t][c];
  276.             o = ban_no_henkan[r] (idou_suru (b, t));
  277.             if (wr[p][o] < min) {
  278.                 min = wr[p][o];
  279.                 m = t;
  280.             }
  281.         }
  282.         t = m;
  283.         b = idou_suru (b, t);
  284.         for (o = b, l = c, m = t, i = 0; i < n; i++) {
  285.             o = ban_wo_motoni_modosu[henkan_rireki[n - 1 - i]] (o);
  286.             l = masu_wo_motoni_modosu[henkan_rireki[n - 1 - i]] (l);
  287.             m = masu_wo_motoni_modosu[henkan_rireki[n - 1 - i]] (m);
  288.         }
  289.         printf ("%c", "U***L*R***D"[m - l + 5]);
  290.         r = masu_wo_ikkasyo_ni_motteiku_tame_ni_hituyouna_henkan_bangou[t][c];
  291.         henkan_rireki[n++] = r;
  292.         p = ikkasyo_ni_matomerareta_genzai_iti_no_bangou[t][c];
  293.         b = ban_no_henkan[r] (b);
  294.     }
  295.     printf (" %d\n\n", n);
  296. }
  297.  
  298. int
  299. main ()
  300. {
  301.     int c;
  302.  
  303.     for (c = 0; c < 25; c++) {
  304.         if (c / 5 > 0) {
  305.             masu_wo_ikkasyo_ni_henkan_suru (c, c - 5);
  306.             ugokeru_masu_wo_motomeru (c, c - 5);
  307.         }
  308.         if (c % 5 > 0) {
  309.             masu_wo_ikkasyo_ni_henkan_suru (c, c - 1);
  310.             ugokeru_masu_wo_motomeru (c, c - 1);
  311.         }
  312.         if (c % 5 < 4) {
  313.             masu_wo_ikkasyo_ni_henkan_suru (c, c + 1);
  314.             ugokeru_masu_wo_motomeru (c, c + 1);
  315.         }
  316.         if (c / 5 < 4) {
  317.             masu_wo_ikkasyo_ni_henkan_suru (c, c + 5);
  318.             ugokeru_masu_wo_motomeru (c, c + 5);
  319.         }
  320.     }
  321.  
  322.     solve_0 ();
  323.  
  324.     solve (0x00000000);
  325.     solve (0x00100000);
  326.     solve (0x00010000);
  327.     solve (0x00001000);
  328.     solve (0x00000100);
  329.     solve (0x00000010);
  330.     solve (0x01649451);
  331. }
  332.  
Time limit exceeded #stdin #stdout 5s 402688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/S7UA0k
language:
C (gcc 8.3)
created:
7 years 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!