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( );
  }
  
  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;
  }
  
  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 )
 break;
      
      if( !theWords[ searchResult ].startsWith( charSequence ) )
 break;
      if( theWords[ searchResult ].equals( charSequence ) )
      {
 numMatches++;
 System.out.println( "发现了 " + charSequence + " 在 " +
    baseRow+1 + "行  " + baseCol + " 列   " +
    i + " " + j );
      }
    }
    return numMatches;
  }
  
  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 puzzleLines = new ArrayList( );
    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 words = new ArrayList( );
    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程序设计有所帮助。