本文實例講述了java實現單詞搜索迷宮遊戲。分享給大家供大家參考。具體分析如下：
我們在雜誌上，經常能夠看到找單詞的小遊戲，在一個二維表格中，存在各種字母，我們可以從八個方向找單詞。這個用計算機處理十分方便，但是，算法的好壞很重要，因為要是用蠻力算法實現，那麼耗費的時間是不可想像的。
這是數據結構與問題求解Java語言描述一書中給的實現思路
完整代碼如下，註釋寫的很明白了
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程序設計有所幫助。