fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <algorithm>
  4. #define LLU unsigned long long
  5. using namespace std;
  6. struct status {
  7.     char board[4][4];
  8.     int ix, iy;
  9. } init;
  10. int pos[16][2], mxdep;
  11. int dir[4][2] = {{0,-1},{-1,0},{1,0},{0,1}};/*u,l,r,d*/
  12. char dirc[4] = {'L', 'U', 'D', 'R'}, path[100];
  13. int solved;
  14. bool solvable() {
  15.     int sum = 0, row, i, j;
  16.     for(i = 0; i < 16; i++) {
  17.         if(init.board[i/4][i%4] == 0) {
  18.             row = i/4 + 1;
  19.             continue;
  20.         }
  21.         for(j = i+1; j < 16; j++) {
  22.             if(init.board[j/4][j%4] < init.board[i/4][i%4]) {
  23.                 if(init.board[j/4][j%4])
  24.                     sum++;
  25.             }
  26.         }
  27.     }
  28.     return 1-(sum+row)%2;
  29. }
  30. int H() {
  31.     static int i, j, sum, num;
  32.     sum = 0;
  33.     for(i = 0; i < 4; i++) {
  34.         for(j = 0; j < 4; j++) {
  35.             num = init.board[i][j];
  36.             if(num == 0)
  37.                 continue;
  38.             sum += abs(i-pos[num][0]) + abs(j-pos[num][1]);
  39.         }
  40.     }
  41.     return sum;
  42. }
  43. int Htable[4][4][16];
  44. int IDA(int dep, int hv, int prestep) {
  45.     if(hv == 0) {
  46.         solved = dep;
  47.         path[dep] = '\0';
  48.         puts(path);
  49.         return dep;
  50.     }
  51.     if(dep + 5*hv/3 > mxdep) {
  52.         return dep + 5*hv/3;
  53.     }
  54.     int i, tx, ty, x = init.ix, y = init.iy;
  55.     int submxdep = 0xfff, val = 0xfff, shv;
  56.  
  57.     for(i = 0; i < 4; i++) {
  58.         if(i + prestep == 3)    continue;
  59.         tx = x + dir[i][0], ty = y + dir[i][1];
  60.         if(tx < 0 || ty < 0 || tx > 3 || ty > 3)
  61.             continue;
  62.  
  63.         shv = hv;
  64.         shv -= Htable[tx][ty][init.board[tx][ty]];
  65.         shv += Htable[x][y][init.board[tx][ty]];
  66.         init.ix = tx, init.iy = ty;
  67.         swap(init.board[x][y], init.board[tx][ty]);
  68.  
  69.         path[dep] = dirc[i];
  70.         val = IDA(dep+1, shv, i);
  71.  
  72.         swap(init.board[x][y], init.board[tx][ty]);
  73.         init.ix = x, init.iy = y;
  74.         if(solved)  return solved;
  75.         submxdep = min(submxdep, val);
  76.     }
  77.     return submxdep;
  78. }
  79. int main() {
  80.     int test, i, j, k, initH;
  81.     int cases = 0;
  82.     for(i = 0, k = 0; i < 4; i++)
  83.         for(j = 0; j < 4; j++)
  84.             pos[++k][0] = i, pos[k][1] = j;
  85.     for(i = 0; i < 4; i++)
  86.         for(j = 0; j < 4; j++)
  87.             for(k = 1; k < 16; k++)
  88.                 Htable[i][j][k] = abs(i - pos[k][0]) + abs(j - pos[k][1]);
  89.     scanf("%d", &test);
  90.     while(test--) {
  91.         cases++;
  92.         for(i = 0; i < 4; i++) {
  93.             for(j = 0; j < 4; j++) {
  94.                 scanf("%d", &k);
  95.                 init.board[i][j] = k;
  96.                 if(init.board[i][j] == 0) {
  97.                     init.ix = i, init.iy = j;
  98.                 }
  99.             }
  100.         }
  101.         if(solvable()) {
  102.             solved = 0, initH = mxdep = H();
  103.             if(!mxdep) {
  104.                 puts("");
  105.                 continue;
  106.             }
  107.             while(solved == 0)
  108.                 mxdep = IDA(0, initH, -1);
  109.             //printf("%d\n", solved);
  110.         }else {
  111.             puts("This puzzle is not solvable.");
  112.         }
  113.     }
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SPmJIH
language:
C++ (gcc 8.3)
created:
10 days 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!