本文实例讲述了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程序设计有所帮助。