软件开发|编程技术|编程代码|编程入门先学什么—程序设计语言

java实现单词搜索迷宫游戏

本文实例讲述了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;    ListString puzzleLines = new ArrayListString( );    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  {    ListString words = new ArrayListString( );    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程序设计有所帮助。