本文实例讲述了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程序设计有所帮助。
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索java
, 单词搜索
迷宫游戏
搜索算法实现迷宫问题、走迷宫游戏的java实现、java实现三维迷宫、java实现迷宫、java搜索功能怎么实现,以便于您获取更多的相关知识。
时间: 2024-10-10 12:03:38