java实现单词搜索迷宫游戏
本文实例讲述了java实现单词搜索迷宫游戏。分享给大家供大家参考。具体分析如下：
我们在杂志上，经常能够看到找单词的小游戏，在一个二维表格中，存在各种字母，我们可以从八个方向找单词。这个用计算机处理十分方便，但是，算法的好坏很重要，因为要是用蛮力算法实现，那么耗费的时间是不可想象的。
这是数据结构与问题求解Java语言描述一书中给的实现思路
完整代码如下，注释写的很明白了
importjava.io.BufferedReader;
importjava.io.FileReader;
importjava.io.InputStreamReader;
importjava.io.IOException;
importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.List;
/**
*单词搜索迷宫
*
**/
publicclassWordSearch
{
/**
*在构造函数中构造两个输入流，单词的输入流，和表格的输入流
**/
publicWordSearch()throwsIOException
{
puzzleStream=openFile("输入表格文件路径：");
wordStream=openFile("输入单词文件路径：");
System.out.println("文件读取中...");
readPuzzle();
readWords();
}
/**
*@returnmatches共有多少个单词匹配
*按照每个位置从八个方向搜索
*rd表示行上得增量，eg:rd=-1，表示向上一行
*cd表示列上得增量eg:cd=-1。表示向左一步
*所以rd=1,cd=0表示南
*rd=-1,cd=0表示北，
*rd=-1,cd=1,表示东北
*/
publicintsolvePuzzle()
{
intmatches=0;
for(intr=0;r<rows;r++)
for(intc=0;c<columns;c++)
for(intrd=-1;rd<=1;rd++)
for(intcd=-1;cd<=1;cd++)
if(rd!=0||cd!=0)
matches+=solveDirection(r,c,rd,cd);
returnmatches;
}
/**
*在指定的坐标上，按照给定的方向搜索，返回匹配的单词数量
*@returnnumberofmatches
*/
privateintsolveDirection(intbaseRow,intbaseCol,introwDelta,intcolDelta)
{
StringcharSequence="";
intnumMatches=0;
intsearchResult;
charSequence+=theBoard[baseRow][baseCol];
for(inti=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);
}
}
returnnumMatches;
}
/**
*先解释Arrays.binarySearch(Object[],Object)
*使用二进制搜索算法来搜索指定数组，以获得指定对象。在进行此调用之前，
*必须根据数组元素的自然顺序对数组进行升序排序（通过上面的Sort(Object[]方法）。
*如果没有对数组进行排序，则结果是不明确的。（如果数组包含不可相互比较的元素（例如，字符串和整数），
*则无法根据数组元素的自然顺序对数组进行排序，因此结果是不明确的。）
*如果数组包含多个等于指定对象的元素，则无法保证找到的是哪一个。
*/
privatestaticintprefixSearch(String[]a,Stringx)
{
intidx=Arrays.binarySearch(a,x);
if(idx<0)
return-idx-1;
else
returnidx;
}
/**
*读取文件内容，获得输入流
*/
privateBufferedReaderopenFile(Stringmessage)
{
StringfileName="";
FileReadertheFile;
BufferedReaderfileIn=null;
do
{
System.out.println(message+":");
try
{
fileName=in.readLine();
if(fileName==null)
System.exit(0);
theFile=newFileReader(fileName);
fileIn=newBufferedReader(theFile);
}
catch(IOExceptione)
{System.err.println("Cannotopen"+fileName);}
}while(fileIn==null);
System.out.println("Opened"+fileName);
returnfileIn;
}
/**
*读入表格
**/
privatevoidreadPuzzle()throwsIOException
{
StringoneLine;
List<String>puzzleLines=newArrayList<String>();
if((oneLine=puzzleStream.readLine())==null)
thrownewIOException("Nolinesinpuzzlefile");
columns=oneLine.length();
puzzleLines.add(oneLine);
while((oneLine=puzzleStream.readLine())!=null)
{
if(oneLine.length()!=columns)
System.err.println("Puzzleisnotrectangular;skippingrow");
else
puzzleLines.add(oneLine);
}
rows=puzzleLines.size();
theBoard=newchar[rows][columns];
intr=0;
for(StringtheLine:puzzleLines)
theBoard[r++]=theLine.toCharArray();
}
/**
*读取已经按照字典排序的单词列表
*/
privatevoidreadWords()throwsIOException
{
List<String>words=newArrayList<String>();
StringlastWord=null;
StringthisWord;
while((thisWord=wordStream.readLine())!=null)
{
if(lastWord!=null&&thisWord.compareTo(lastWord)<0)
{
System.err.println("没有按照字典顺序排序，此次跳过");
continue;
}
words.add(thisWord.trim());
lastWord=thisWord;
}
theWords=newString[words.size()];
theWords=words.toArray(theWords);
}
//Cheapmain
publicstaticvoidmain(String[]args)
{
WordSearchp=null;
try
{
p=newWordSearch();
}
catch(IOExceptione)
{
System.out.println("IOError:");
e.printStackTrace();
return;
}
System.out.println("正在搜索...");
p.solvePuzzle();
}
privateintrows;
privateintcolumns;
privatechar[][]theBoard;
privateString[]theWords;
privateBufferedReaderpuzzleStream;
privateBufferedReaderwordStream;
privateBufferedReaderin=newBufferedReader(newInputStreamReader(System.in));
}
希望本文所述对大家的java程序设计有所帮助。