wordpuzzle.java

在一个n*n 矩阵中找到 沿着八个方向搜索

package cn.edu.nju.software.puzzle;

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class WordPuzzle {
	String[][] letters;
	int rownumOfsquare;
	int vernumOfsquare;
	BufferedReader keybordOne,keybordTow;	
	private ArrayList<String> dictString=new ArrayList<String>();
	
	public WordPuzzle(File squareFile, File dictFile){		
		try {
			keybordOne = new BufferedReader(new FileReader(squareFile));
			StringTokenizer tokenizerOne=new StringTokenizer(keybordOne.readLine());
			rownumOfsquare=tokenizerOne.countTokens();
			vernumOfsquare=tokenizerOne.countTokens();
			letters=new String[rownumOfsquare][vernumOfsquare];
			for(int i=0;i<rownumOfsquare;i++){
			 for(int j=0;j<vernumOfsquare;j++){
				letters[i][j]=tokenizerOne.nextToken();			
				}
			 String str=keybordOne.readLine();
			 if(str!=null)
				 tokenizerOne=new StringTokenizer(str);
			 }
		} catch (FileNotFoundException e) {
			
			e.printStackTrace();
		} catch (IOException e) {
			
			e.printStackTrace();
		}	
		
		try {
			keybordTow = new BufferedReader(new FileReader(dictFile));
			String temp=keybordTow.readLine();
			while(temp!=null){
				dictString.add(temp);
				temp=keybordTow.readLine();			
			}
		} catch (FileNotFoundException e) {
			
			e.printStackTrace();
		} catch (IOException e) {
			
			e.printStackTrace();
		}
		
		
	}
		
	
	
	public Set<String> find() {
		HashSet<String> dictWord=new HashSet<String>();		
		for(int i=0;i<rownumOfsquare;i++){
			for(int j=0;j<vernumOfsquare;j++){
				String testString="";
				for(int index=0;index+j<vernumOfsquare;index++){
					testString=testString+letters[i][j+index];
				if(testString.length()>4&&binarySearch(dictString,testString))
					dictWord.add(testString);
				}
			}
		}
		for(int i=0;i<rownumOfsquare;i++){
			for(int j=0;j<vernumOfsquare;j++){
			String testString="";
				for(int index=0;j-index>=0;index++){					
					testString=testString+letters[i][j-index];
					if(testString.length()>4&&binarySearch(dictString,testString))
						dictWord.add(testString);
				}
			}
		}
		for(int j=0;j<vernumOfsquare;j++){
			for(int i=0;i<rownumOfsquare;i++){
			String testString="";
				for(int index=0;index+i<vernumOfsquare;index++){				
				testString=testString+letters[i+index][j];
				if(testString.length()>4&&binarySearch(dictString,testString))
					dictWord.add(testString);
				}
			}
		}	
		for(int j=0;j<vernumOfsquare;j++){
			for(int i=rownumOfsquare-1;i>=0;i--){
			String testString="";
				for(int index=0;i-index>=0;index++){				
					testString=testString+letters[i-index][j];
					if(testString.length()>4&&binarySearch(dictString,testString))
						dictWord.add(testString);
				}
			}
		}
		for(int i=0;i<rownumOfsquare;i++){
			for(int j=0;j<vernumOfsquare;j++){
				String testString="";
				for(int index=0;index+j<vernumOfsquare&&index+i<rownumOfsquare;index++){			
				testString=testString+letters[i+index][j+index];
				if(testString.length()>4&&binarySearch(dictString,testString))
					dictWord.add(testString);
				}
			}
		}
		for(int i=0;i<rownumOfsquare;i++){
			for(int j=0;j<vernumOfsquare;j++){
				String testString="";
				for(int index=0;index+i<vernumOfsquare&&j-index>=0;index++){				
				testString=testString+letters[i+index][j-index];
				if(testString.length()>4&&binarySearch(dictString,testString))
					dictWord.add(testString);
				}
			}
		}
		for(int j=0;j<vernumOfsquare;j++){
			for(int i=rownumOfsquare-1;i>=0;i--){
				String testString="";
				for(int index=0;i-index>=0&&index+j<vernumOfsquare;index++){				
					testString=testString+letters[i-index][j+index];
					if(testString.length()>4&&binarySearch(dictString,testString))
						dictWord.add(testString);
				}
			}
		}
		for(int j=0;j<vernumOfsquare;j++){
			for(int i=rownumOfsquare-1;i>=0;i--){
				String testString="";
				for(int index=0;j-index>=0&&i-index>=0;index++){				
					testString=testString+letters[i-index][j-index];
					if(testString.length()>4&&binarySearch(dictString,testString))
						dictWord.add(testString);
				}
			}
		}
		
		if(dictWord.size()==0)
			return null;
		else
					return dictWord;
		
}
	public boolean binarySearch(ArrayList<String> list,String item){
		boolean found=false;
		int first=0;
		int last=list.size()-1;
		int mid;
		while(first<=last&&!found){
			mid=(first+last)/2;
			if(list.get(mid).equals(item))
				found=true;
			else
				if(list.get(mid).compareTo(item)<0)
					first=mid+1;
					
				else
					
					last=mid-1;
			
		}
		return found;
		
		
	}
}