java实现单词搜索迷宫游戏_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程序设计有所帮助。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索java
, 单词搜索
迷宫游戏
搜索算法实现迷宫问题、走迷宫游戏的java实现、java实现三维迷宫、java实现迷宫、java搜索功能怎么实现,以便于您获取更多的相关知识。

时间: 2024-10-10 12:03:38

java实现单词搜索迷宫游戏_java的相关文章

java编写贪吃蛇小游戏_java

废话不多说,直接奉上代码: Frame.java package snake; import java.awt.Graphics; import java.awt.Menu; import java.awt.MenuBar; import java.awt.MenuItem; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.KeyEvent; import

Java完美实现2048小游戏_java

完美地模仿了2048游戏,是根据网友的一个2048改的. Block.java import javax.swing.*; import java.awt.*; public class Block extends JLabel { private int value; public Block() { value = 0;//初始化值为0 setFont(new Font("font", Font.PLAIN, 40));//设定字体 setBackground(Color.gray

经典再现 基于JAVA平台开发坦克大战游戏_java

一.需求描述 1.功能性需求 在功能需求分析阶段,我们的主要任务是指定系统必须提供哪些服务,定义软件完成哪些功能,提供给那些人使用,功能需求是软件开发的一项基本需求,是需求分析必不可少的一部分.坦克大战是一款经典游戏了,本游戏学习了一些前辈们的经验,整体来说讲,游戏分为敌我双方,主要参与战斗的坦克有玩家控制,敌人坦克可以智能随机出现在屏幕上,并且移动,发射一定数量的子弹:玩家可以在规定的区域内随意移动坦克,当有子弹击中玩家时,玩家死亡,游戏结束:敌人坦克智能运行,敌方坦克由于需要具有一定智能性,

java实现单人版五子棋游戏_java

本文实例讲述了java实现的五子棋游戏代码,分享给大家供大家参考,具体代码如下 package gyb.exam; import java.awt.BorderLayout; import java.awt.Color; import java.awt.Dimension; import java.awt.Font; import java.awt.Graphics; import java.awt.Point; import java.awt.Toolkit; import java.awt.

java实现简单美女拼图游戏_java

拼图小游戏,学习阶段.很多不足,改进了一下 演示图片: J_Puzzle.java import java.awt.BorderLayout; import java.awt.Component; import java.awt.Container; import java.awt.Dimension; import java.awt.Font; import java.awt.Graphics; import java.awt.GridBagConstraints; import java.a

Java编写猜数字小游戏_java

本文实例讲述了java实现的简单猜数字游戏代码.分享给大家供大家参考. 以下是Java语言写的一个猜数字小游戏引用片段: import java.text.SimpleDateFormat; import java.util.Date; import java.util.Scanner; //主函数 public class calssOne { public static void main(String[] args) { //shit+Ctrl+o int result; //随机产生一个

微信游戏打飞机游戏制作(java模拟微信打飞机游戏)_java

复制代码 代码如下: package com.beancore.ui; import java.awt.BorderLayout;import java.awt.Container;import java.awt.Dimension;import java.awt.Toolkit;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.io.IOException;import java

利用java实现单词倒序排列_java

本文就是会将数组里面的单词进行倒序排列 例如 how old are you -> you are old how 示例程序输出结果: the first: How old are you !? I don't understand the second: understand don't I ?! you are old How 示例代码     public static void main(String[] args) { char[] chars= new String("How

Java编写掷骰子游戏_java

废话不多说了,直接奔主题. **多线程&&观察者模式 题目要求:<掷骰子>窗体小游戏,在该游戏中,玩家初始拥有1000的金钱,每次输入押大还是押小,以及下注金额,随机3个骰子的点数,如果3个骰子的总点数小于等于9,则开小,否则开大,然后判断玩家是否押对,如果未押对则扣除下注金额,如果押对则奖励和玩家下注金额相同的金钱. 分析:这个题目要求灵活运用多线程的相关知识,达到点击开始按钮时,有3个线程启动,分别控制3颗骰子的转动,在3颗骰子全部转完以后,回到主线程计算游戏结果. //个