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;
    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程序设计有所帮助。