蛮力法解字谜游戏

时差爆发，睡不着，闲的蛋疼。。。思路写在注释里，直接撸代码：

import java.util.*;  
public class WordPuzzle {  
    private char[][] puzzle;  
    private List<String> wordList;  
    public WordPuzzle(char[][] puzzle, List<String> wordList) {  
        this.puzzle = puzzle;  
        this.wordList = wordList;  
    }

    /** 
     * Solve the puzzle.<br/> 
     * result: {beginIndex(row, column);endIndex(row, column);matchWord}<br/> 
     * temp tuple: {beginIndex(row,column);endIndex(row,column);direction;composedChars2String}<br/>
     * Procedure:<br/> 
     * for each element in the puzzle {<br/> 
     *     construct a tuple;<br/> 
     *     check word list and see whether there is a match;<br/> 
     * }
     */  
    public List<String> solvePuzzle() {  
        List<String> resultList = new LinkedList<String>();  
        List<String> tupleList = null;  
        String tempResult = null;  
        String[] strings = null;  
        for(int i = 0; i < puzzle.length; i++) {  
            for(int j = 0; j < puzzle[i].length; j++) {  
                tupleList = findAllString(i, j);
                System.out.println("Tuple list constructed.");
                for(String temp : tupleList) {
                    System.out.println(temp);
                    if(temp != null) {
                        strings = temp.split(";");
                        System.out.println("judging " + strings[0]);
                        if(wordList.contains(strings[0])) {
                            tempResult = "(" + i + "," + j + ");" + strings[1] + ";" + strings[0];
                            resultList.add(tempResult);
                        }
                    }
                } 
            } 
        }
        Iterator<String> iterator = resultList.iterator();
        String temp = null;
        while(iterator.hasNext()) {
            temp = iterator.next();
            if(temp == null || "null".equals(temp)) {
                iterator.remove();
            }
        }
        return resultList;
    }  

    /** 
     * Find all possible composed strings and return as a list along with the end index.<br/> 
     * eg. {string;(row,column)} 
     */
    private List<String> findAllString(int beginRow, int beginColumn) {
        List<String> resultList = new LinkedList<String>();
        List<String> tempList = null;
        if(beginColumn < puzzle[beginRow].length - 1) {
            tempList = findAllRow(beginRow, beginColumn);
            appendList(resultList, tempList);
            tempList.clear();
        }
        if(beginColumn < puzzle.length - 1) {
            tempList = findAllColumn(beginRow, beginColumn); 
            appendList(resultList, tempList);
            tempList.clear();
        }
        if((beginColumn < puzzle.length - 1) && (beginColumn < puzzle[beginRow].length - 1)) {
            tempList = findAllDiagonal(beginRow, beginColumn); 
            appendList(resultList, tempList);
            tempList.clear();
        }
        return resultList; 
    }

    /**
     * Appends each element form the src list to the destination list.
     */
    public <T> void appendList(List<T> dest, List<T> src) {
        for (T temp : src) {
            dest.add(temp);
        }
    }

    /**
     * Find all possible composed words in the same row starting at a given index.
     */ 
    private List<String> findAllRow(int i, int j) {
        List<String> tempWords = new LinkedList<String>();
        StringBuilder sb = new StringBuilder(); // Hold the words and their indexes.
        StringBuilder sbw = new StringBuilder(); // Hold the composed words.
        if(j < puzzle[i].length - 1) {
            sbw.append(puzzle[i][j]);
            for(int a = j + 1; a < puzzle[i].length; a++) {
                sbw.append(puzzle[i][a]);
                sb.append(sbw.toString()).append(";(")
                    .append(i).append(',').append(a).append(')');
                System.out.println(sbw.toString());
                System.out.println(sb.toString());
                tempWords.add(sb.toString());
                sb.delete(0, sb.length()); // Empty the sb.
            }
        }
        return tempWords;
    }

    /**
     * Find all possible composed words in the same column starting at a given index.
     */
    private List<String> findAllColumn(int i, int j) {
        List<String> tempWords = new LinkedList<String>();
        StringBuilder sb = new StringBuilder(); // Hold the words and their indexes.
        StringBuilder sbw = new StringBuilder(); // Hold the composed words.
        if(i < puzzle.length - 1) {
            sbw.append(puzzle[i][j]);
            for(int a = i + 1; a < puzzle.length; a++) {
                sbw.append(puzzle[a][j]);
                sb.append(sbw.toString()).append(";(")
                    .append(a).append(',').append(j).append(')');
                System.out.println(sbw.toString());
                System.out.println(sb.toString());
                tempWords.add(sb.toString());
                sb.delete(0, sb.length()); // Empty the sb.
            }
        }
        return tempWords;
    }


    /**
     * Find all possible composed words in the diagonal starting at a given index.
     */
    private List<String> findAllDiagonal(int i, int j) {
        List<String> tempWords = new LinkedList<String>();
        StringBuilder sb = new StringBuilder();
        StringBuilder sbw = new StringBuilder();
        if(i < puzzle.length - 1 && j < puzzle[i].length - 1) {
            sbw.append(puzzle[i][j]);
            for(int a = i + 1, b = j + 1; a < puzzle.length && b < puzzle[a].length; a++, b++) {
                sbw.append(puzzle[a][b]);
                sb.append(sbw.toString()).append(";(")
                    .append(a).append(',').append(b).append(')');
                System.out.println(sbw.toString());
                System.out.println(sb.toString());
                tempWords.add(sb.toString());
                sb.delete(0, sb.length()); // Empty the sb.
            }
        }
        return tempWords;
    }

    public static void main(String[] args) {
        List<String> dictionary = new ArrayList<String>();
        Collections.addAll(dictionary, new String[]{"dad", "cat", "sad", "sat", "bad"});
        char[][] myPuzzle = new char[4][4];
        myPuzzle[0] = new char[] {'i', 'd', 'a', 'd'};
        myPuzzle[1] = new char[] {'w', 's', 'a', 'd'};
        myPuzzle[2] = new char[] {'v', 'b', 'a', 'd'};
        myPuzzle[3] = new char[] {'z', 'c', 'a', 't'};
        WordPuzzle wp = new WordPuzzle(myPuzzle, dictionary);
        List<String> results = wp.solvePuzzle();
        System.out.println("the result is: ");
        for(String temp : results) {
            System.out.println(temp);
        }
    }
}

 

运行结果：

the result is:
(0,1);(0,3);dad
(0,1);(2,3);dad
(1,1);(1,3);sad
(1,1);(3,3);sat
(2,1);(2,3);bad
(3,1);(3,3);cat