杭电1043java实现bfs一遍

题目Eight

Problem Description

这个15难题已经存在了100多年了，即使你不知道它的名字，你也看到了。它由15个滑动瓦片构成，每个滑动瓦片的数量从1到15，并且全部装入4乘4帧，缺少一个瓦片。我们称之为缺失的瓦片’x’;难题的目的是安排瓷砖，以便它们按以下顺序排列：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 x

其中唯一合法的操作是与其共享边缘的一个瓷砖交换’x’。作为一个例子，下面的一系列动作解决了一个稍微混乱的难题：

1 2 3 4 -> 1 2 3 4 -> 1 2 3 4 -> 1 2 3 4

5 6 7 8 -> 5 6 7 8 -> 5 6 7 8 -> 5 6 7 8

9 x 10 12 -> 9 10 x 12 -> 9 10 11 12 -> 9 10 11 12

13 14 11 15 -> 13 14 11 15 -> 13 14 x 15 -> 13 14 15 x

r-> d-> r->

上一行中的字母表示每个步骤中’x’瓦片的哪个邻居与’x’瓦片交换;法律价值分别为’r’，‘l’，‘u’和’d’，分别为正，左，上和下。

并非所有的谜题都可以解决;在1870年，一个名叫萨姆·洛伊德的人因发布了一个难以解决的难题而闻名

挫败了很多人。事实上，只需要交换两块拼块（当然，不包括缺失的“x”拼块），您所需要做的就是拼成一个难以解决的难题。

在这个问题中，你将编写一个程序来解决不太知名的8拼图，它是由3×3的拼图组成的安排。

输入

您将收到有关8拼图配置的几个说明。一个描述只是一个在其初始位置的图块列表，其中行从上到下列出，并且在一行内从左到右列出图块，其中图块由数字1到8表示，再加上’x’ 。例如，这个难题

1 2 3

x 4 6

7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

Output

如果拼图没有解决方案，或者将完全由字母’r’，‘l’，'u’和’d’组成的字符串描述为一系列移动产生一个解决方案。该字符串不应包含空格，并从行首开始。不要在案件之间打印空行。

Sample Input

2 3 4 1 5 x 7 6 8

Sample Output

ullddrurdllurdruldr

问题分析：因为有多组测试数据，我使用的是bfs 康托，bfs跑一遍，遍历所有情况，然后输出输入的值，我把初始数组变为123456789，因为输入的x和9在字符串大小是等效的。值得注意的是路径要倒着写，因为我们走的过程是取反过程。还有注意的是一维二维数组的转换，计算康托值用一维数组，但是移动要变成二维注意Java的对象克隆，不然你的数组会被更改。

还有大佬用A*和双向bfs的可以了解下。方法也很巧妙。

贴上代码

import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class 杭电1043 { static int jiecheng[]= {1,1,2,6,24,120,720,5040,40320}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); char start[][]= {{'1','2','3'},{'4','5','6'},{'7','8','9'}}; //初始状态 int judgel[]=new int[362880];//标记 String path []=new String [362880];//记录路径 Queue q1=new ArrayDeque(); judgel[0]=1;path[0]="";//初始化（0到0要特殊处理） q1.add(start);//入队 while(!q1.isEmpty()) { char[][]exa=q1.poll(); int kang=kangtuo(exa);//对应的位置; int x1=0,y1=0; for(int i=0;i<3;i )//找打'x'（9）的位置 { for(int j=0;j<3;j ) { if(exa[i][j]=='9') {x1=i;y1=j;} } } int k2=0; //执行bfs {char[][]t2=r(exa,x1,y1); k2=kangtuo(t2);if(judgel[k2]==0) {q1.add(t2);path[k2]='l' path[kang];judgel[k2]=1;}} {char[][]t1=l(exa,x1,y1); k2=kangtuo(t1);if(judgel[k2]==0) {q1.add(t1);path[k2]='r' path[kang];judgel[k2]=1;}} {char[][]t4=down(exa,x1,y1); k2=kangtuo(t4);if(judgel[k2]==0) {q1.add(t4);path[k2]='u' path[kang];judgel[k2]=1;}} {char[][]t3=up(exa,x1,y1); k2=kangtuo(t3);if(judgel[k2]==0) {q1.add(t3);path[k2]='d' path[kang];judgel[k2]=1;}} } while(sc.hasNextLine()) { String a=sc.nextLine(); String a2[]=a.split(" "); char c[][]=new char[3][3]; for(int i=0;i<9;i ) { c[i/3][i%3]=a2[i].charAt(0); } String value=path[kangtuo(c)];//直接输出保存过的值 if(value==null) {System.out.println("unsolvable"); } else if(value=="") {System.out.println("lr");} else System.out.println(value); } } static int kangtuo(char[][] start) { int m=0;int n=0; char b[]=new char[9]; for(int i=0;i<3;i ) { for(int j=0;j<3;j ) b[i*3 j]=start[i][j]; } for(int i=0;i<9;i ) { m=0; for(int j=i 1;j<9;j ) { if(b[i]>b[j])m ; } n =m*jiecheng[8-i]; } return n; } static char[][] l (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(y1>0) { char team=b[x1][y1]; b[x1][y1]=b[x1][y1-1]; b[x1][y1-1]=team;} return b; } static char[][] r (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(y1<2) { char team=b[x1][y1]; b[x1][y1]=b[x1][y1 1]; b[x1][y1 1]=team;} return b; } static char[][] up (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(x1==1||x1==2) { char team=b[x1][y1]; b[x1][y1]=b[x1-1][y1]; b[x1-1][y1]=team;} return b; } static char[][] down (char a[][],int x1,int y1) { char b[][]=new char[3][3]; b[0]=a[0].clone(); b[1]=a[1].clone(); b[2]=a[2].clone(); if(x1==0||x1==1) { char team=b[x1][y1]; b[x1][y1]=b[x1 1][y1]; b[x1 1][y1]=team;} return b; } }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

Java 数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。