本文实例讲述了java实现单词搜索迷宫游戏。分享给大家供大家参考。具体分析如下：
我们在杂志上，经常能够看到找单词的小游戏，在一个二维表格中，存在各种字母，我们可以从八个方向找单词。这个用计算机处理十分方便，但是，算法的好坏很重要，因为要是用蛮力算法实现，那么耗费的时间是不可想象的。
这是数据结构与问题求解Java语言描述一书中给的实现思路
完整代码如下，注释写的很明白了
|
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
import java.io.BufferedReader;import java.io.FileReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * 单词搜索迷宫 * * */public class WordSearch{ /** * 在构造函数中构造两个输入流，单词的输入流，和表格的输入流 * */ public WordSearch( ) throws IOException { puzzleStream = openFile( "输入表格文件路径：" ); wordStream = openFile( "输入单词文件路径：" ); System.out.println( "文件读取中..." ); readPuzzle( ); readWords( ); } /** * @return matches 共有多少个单词匹配 * 按照每个位置从八个方向搜索 * rd 表示行上得增量，eg:rd=-1，表示向上一行 * cd 表示列上得增量 eg:cd=-1。表示向左一步 * 所以rd=1,cd=0表示南 * rd=-1,cd=0表示北， * rd=-1,cd=1,表示东北 */ public int solvePuzzle( ) { int matches = 0; for( int r = 0; r < rows; r++ ) for( int c = 0; c < columns; c++ ) for( int rd = -1; rd <= 1; rd++ ) for( int cd = -1; cd <= 1; cd++ ) if( rd != 0 || cd != 0 ) matches += solveDirection( r, c, rd, cd ); return matches; } /** * 在指定的坐标上，按照给定的方向搜索，返回匹配的单词数量 * @return number of matches */ private int solveDirection( int baseRow, int baseCol, int rowDelta, int colDelta ) { String charSequence = ""; int numMatches = 0; int searchResult; charSequence += theBoard[ baseRow ][ baseCol ]; for( int i = baseRow + rowDelta, j = baseCol + colDelta; i >= 0 && j >= 0 && i < rows && j < columns; i += rowDelta, j += colDelta ) { charSequence += theBoard[ i ][ j ]; searchResult = prefixSearch( theWords, charSequence ); /** * 下面的 if( searchResult == theWords.length ) * 必须要判断，否则会出现越界的危险，及当最后一个单词之匹配前缀时，返回的是索引-1 * */ if( searchResult == theWords.length ) break; /** * 如果没有响应的前缀，直接跳过这个基点的搜索，即使继续搜索，做的也是无用功 * */ if( !theWords[ searchResult ].startsWith( charSequence ) ) break; if( theWords[ searchResult ].equals( charSequence ) ) { numMatches++; System.out.println( "发现了 " + charSequence + " 在 " + baseRow+1 + "行 " + baseCol + " 列 " + i + " " + j ); } } return numMatches; } /** * 先解释Arrays.binarySearch(Object[] ,Object) * 使用二进制搜索算法来搜索指定数组，以获得指定对象。在进行此调用之前， * 必须根据数组元素的自然顺序 对数组进行升序排序（通过上面的 Sort(Object[] 方法）。 * 如果没有对数组进行排序，则结果是不明确的。（如果数组包含不可相互比较的元素（例如，字符串和整数）， * 则无法 根据数组元素的自然顺序对数组进行排序，因此结果是不明确的。） * 如果数组包含多个等于指定对象的元素，则无法保证找到的是哪一个。 */ private static int prefixSearch( String [ ] a, String x ) { int idx = Arrays.binarySearch( a, x ); if( idx < 0 ) return -idx - 1; else return idx; } /** * 读取文件内容，获得输入流 */ private BufferedReader openFile( String message ) { String fileName = ""; FileReader theFile; BufferedReader fileIn = null; do { System.out.println( message + ": " ); try { fileName = in.readLine( ); if( fileName == null ) System.exit( 0 ); theFile = new FileReader( fileName ); fileIn = new BufferedReader( theFile ); } catch( IOException e ) { System.err.println( "Cannot open " + fileName ); } } while( fileIn == null ); System.out.println( "Opened " + fileName ); return fileIn; } /** * 读入表格 * */ private void readPuzzle( ) throws IOException { String oneLine; List<String> puzzleLines = new ArrayList<String>( ); if( ( oneLine = puzzleStream.readLine( ) ) == null ) throw new IOException( "No lines in puzzle file" ); columns = oneLine.length( ); puzzleLines.add( oneLine ); while( ( oneLine = puzzleStream.readLine( ) ) != null ) { if( oneLine.length( ) != columns ) System.err.println( "Puzzle is not rectangular; skipping row" ); else puzzleLines.add( oneLine ); } rows = puzzleLines.size( ); theBoard = new char[ rows ][ columns ]; int r = 0; for( String theLine : puzzleLines ) theBoard[ r++ ] = theLine.toCharArray( ); } /** * 读取已经按照字典排序的单词列表 */ private void readWords( ) throws IOException { List<String> words = new ArrayList<String>( ); String lastWord = null; String thisWord; while( ( thisWord = wordStream.readLine( ) ) != null ) { if( lastWord != null && thisWord.compareTo( lastWord ) < 0 ) { System.err.println( "没有按照字典顺序排序，此次跳过" ); continue; } words.add( thisWord.trim() ); lastWord = thisWord; } theWords = new String[ words.size( ) ]; theWords = words.toArray( theWords ); } // Cheap main public static void main( String [ ] args ) { WordSearch p = null; try { p = new WordSearch( ); } catch( IOException e ) { System.out.println( "IO Error: " ); e.printStackTrace( ); return; } System.out.println( "正在搜索..." ); p.solvePuzzle( ); } private int rows; private int columns; private char [ ][ ] theBoard; private String [ ] theWords; private BufferedReader puzzleStream; private BufferedReader wordStream; private BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );} |
希望本文所述对大家的java程序设计有所帮助。
