本文實例講述了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程序設計有所幫助。
