fork(1) download
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.HashSet;
  4. import java.util.PriorityQueue;
  5. import java.util.Set;
  6.  
  7. public class Main {
  8. public static void main(String[] args) throws Exception {
  9. BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  10. int n = Integer.parseInt(bufferedReader.readLine().trim());
  11. int[][] coord = {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};
  12. long value;
  13. long board = (1L << 36) - 1;
  14. long answer = 0;
  15. long cur = 0, check;
  16. long oneCount = ((2L << 50) + (2L << 40));
  17. int r, c, nr, nc, index, num;
  18. int[][] d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
  19. for(long i = 1; i < 9; i++) {
  20. answer |= i << ((i - 1) * 4);
  21. }
  22. Set<Long> impossible = new HashSet<>();
  23. Set<Long> tmp = new HashSet<>();
  24. Set<Long> set = new HashSet<>();
  25. char[][] arr = new char[3][3];
  26. boolean im;
  27. PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
  28. StringBuilder stringBuilder = new StringBuilder();
  29. for(int t = 1; t <= n; t++) {
  30. bufferedReader.readLine();
  31. arr[0] = bufferedReader.readLine().trim().toCharArray();
  32. arr[1] = bufferedReader.readLine().trim().toCharArray();
  33. arr[2] = bufferedReader.readLine().trim().toCharArray();
  34. value = 0;
  35. for(int i = 0; i < 3; i++) {
  36. for(int j = 0; j < 3; j++) {
  37. if(arr[i][j] == '#') {
  38. value += (long)(Math.abs(i - 2) + Math.abs(j - 2)) << 50;
  39. value += ((long)(i * 3 + j) << 36);
  40. } else {
  41. value += (long)(Math.abs(i - coord[arr[i][j] - '1'][0]) + Math.abs(j - coord[arr[i][j] - '1'][1])) << 50;
  42. value |= (long)((arr[i][j] - '0')) << ((i * 3 + j) * 4);
  43. }
  44. }
  45. }
  46. tmp.clear();
  47. im = true;
  48. check = value & board;
  49. if(!impossible.contains(check)) {
  50. priorityQueue.clear();
  51. priorityQueue.offer(value);
  52. set.clear();
  53. set.add(check);
  54. tmp.add(check);
  55. im = false;
  56. while (!priorityQueue.isEmpty()) {
  57. cur = priorityQueue.poll();
  58. if ((cur & board) == answer) {
  59. stringBuilder.append(cur >> 51).append('\n');
  60. break;
  61. }
  62. int i = (int) ((cur >> 36) & 15L);
  63. r = coord[i][0];
  64. c = coord[i][1];
  65. for (int j = 0; j < 4; j++) {
  66. value = cur - ((long) (Math.abs(r - 2) + Math.abs(c - 2)) << 50);
  67. nr = r + d[j][0];
  68. nc = c + d[j][1];
  69. if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
  70. index = nr * 3 + nc;
  71. num = (int) ((cur >> (index * 4)) & 15) - 1;
  72. value &= (~(15L << (index * 4)));
  73. value |= ((long) (num + 1) << (i * 4));
  74. check = value & board;
  75. if(impossible.contains(check)) {
  76. im = true;
  77. break;
  78. }
  79. if (set.contains(check)) {
  80. continue;
  81. }
  82. value += ((long) (Math.abs(nr - 2) + Math.abs(nc - 2)) << 50);
  83. value -= ((long) (Math.abs(coord[num][0] - nr) + Math.abs(coord[num][1] - nc)) << 50);
  84. value += ((long) (Math.abs(coord[num][0] - r) + Math.abs(coord[num][1] - c)) << 50);
  85. value += oneCount;
  86. value = ((value & ~(15L << 36)) | (((long) (nr * 3 + nc)) << 36));
  87. set.add(check);
  88. tmp.add(check);
  89. priorityQueue.offer(value);
  90. }
  91. }
  92. if(im) {
  93. break;
  94. }
  95. }
  96. }
  97. if(im || (cur & board) != answer) {
  98. impossible.addAll(tmp);
  99. stringBuilder.append("impossible\n");
  100. }
  101. }
  102. System.out.print(stringBuilder);
  103. }
  104. }
  105.  
Time limit exceeded #stdin #stdout 5s 238552KB
stdin
100

867
254
3#1

647
85#
321

876
543
21#

87#
546
321

87#
546
213

87#
456
123

87#
426
351

87#
256
341

867
542
31#

867
521
34#

867
514
32#

867
5#4
312

867
5#1
324

867
4#5
321

867
254
31#

867
254
#31

867
241
35#

867
2#4
351

867
1#4
325

865
271
34#

864
7#5
123

863
571
#24

861
274
35#

86#
754
123

86#
475
123

86#
275
341

857
261
34#

857
146
#23

853
762
#41

851
2#4
367

85#
467
123

847
652
31#

847
265
31#

847
156
32#

832
547
61#

831
564
#27

821
364
#57

82#
571
364

786
543
12#

786
435
12#

786
425
#31

786
154
23#

786
154
#23

785
463
12#

785
4#6
123

785
261
34#

78#
653
421

78#
456
321

78#
436
125

78#
154
326

687
251
34#

67#
485
123

658
721
43#

657
842
31#

657
821
34#

657
814
32#

657
8#4
312

657
8#1
324

657
438
#12

657
324
#81

654
321
87#

654
321
#87

65#
834
712

65#
784
123

647
851
32#

647
835
12#

647
832
51#

647
832
#51

647
825
31#

647
8#5
321

647
582
31#

647
5#8
123

647
352
#81

647
281
35#

64#
857
321

631
854
#27

631
8#4
257

63#
582
741

627
8#4
351

627
345
#81

621
834
#57

621
584
#37

621
354
#87

617
8#4
325

617
254
38#

61#
524
387

587
642
31#

587
621
34#

587
2#4
361

58#
476
123

578
4#6
123

578
326
#41

57#
468
123

57#
342
681

57#
268
341

563
8#2
741

547
6#8
321

547
382
#61

547
218
36#

521
634
#87

stdout
Standard output is empty