`
lixuanbin
  • 浏览: 137483 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

蛮力法解字谜游戏

阅读更多

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

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

 

分享到:
评论

相关推荐

    Python 中的字谜游戏

    在Python编程中,创建一个字谜游戏是一种有趣的实践,它能帮助学习者加深对语言特性的理解。这个项目的目标是构建一个游戏,用户需要在有限的尝试次数内猜出一个单词,游戏会给出一些提示来帮助用户。让我们深入探讨...

    Java作业4字谜游戏.zip

    在本Java作业中,我们关注的是“字谜游戏”的实现,这是一个常见的编程练习,旨在提升学生对字符串操作、条件逻辑以及面向对象编程的理解。在这个项目中,学生通常会被要求设计并实现一个字谜游戏,玩家需要通过提示...

    netbeans字谜游戏

    "NetBeans字谜游戏"是一款基于NetBeans IDE开发的小型应用程序,主要功能是提供一个交互式的字谜游戏体验。NetBeans是一个开源的集成开发环境,它支持多种编程语言,包括Java,这使得开发者能够利用其丰富的功能来...

    c语言数独字谜游戏课程设计.doc

    C语言数独字谜游戏课程设计 C语言数独字谜游戏课程设计是基于VC++6.0环境下所开发的程序,旨在实现一个完整的数独游戏。游戏的主要功能包括难度选择、游戏过程、游戏通关和退出游戏等。 技术路线: * 使用VC++6.0...

    数独字谜解法

    对于数独字谜的解法,程序简介,适合初学者使用。节省时间试试看裁决之镰测试正常上课尝试几次生产基地参加第几

    40个有趣的英语字谜游戏.pdf

    40个有趣的英语字谜游戏.pdf

    字谜_数据库脚本

    汉字字谜,已经整理成数据库脚本可直接导入,总计3860个。

    字谜大全及答案.txt

    字谜大全及答案.

    一个简单的字谜算法

    标题“一个简单的字谜算法”指的是在编程领域中设计的一种用于解决字谜问题的算法。字谜通常涉及找出隐藏在单词或短语中的特定模式,这可能涉及到字母位置的替换、颠倒或移位。在这个特定的例子中,我们可能会探讨一...

    15字谜

    玩15字谜的很不错哦

    matlab开发-matlab竞赛纵横字谜

    可能涉及到字符串处理(如strfind、split函数)、矩阵操作(如逻辑索引、线性索引)、回溯法、深度优先搜索等算法。此外,可能还需要使用到MATLAB的单元数组和cell数组来处理不规则数据。 4. **testsuite_sample....

    3d阿福图库字谜总汇.doc

    3d阿福图库字谜总汇.doc

    字谜集锦,可以和学生一起互动.doc

    字谜集锦是指通过游戏、挑战和互动方式来学习汉字的方法。这种方法可以激发学生的兴趣和热情,让他们更好地记忆和掌握汉字。下面是字谜集锦的详细知识点: 1. 字谜的种类:字谜可以分为多种,如谜语谜、图谜、音谜...

    小学数学数学神探同一字谜

    【小学数学数学神探同一字谜】这个主题源自一个经典的中国文化故事,涉及到古代文人的智慧游戏——字谜。字谜是一种巧妙的语言游戏,...通过这样的字谜游戏,可以锻炼孩子们的逻辑思维、观察力和对中国传统文化的理解。

    字谜大全(附答案).doc

    解决字谜需要对汉字结构有深入的理解,同时发挥想象力。通过这样的游戏,可以锻炼思维敏捷度,提高语言文字能力。不过,由于字谜解析需要根据谜面的具体含义进行,每个谜面的解析可能会有所不同,以上只是根据提供的...

    c++猜字游戏

    已经做好的程序,也行对某些人有用

    疯狂猜成语源码

    同时,结果页面可能会包含游戏分享功能,鼓励玩家将游戏成果分享到微信朋友圈,从而增加游戏的传播力。 总的来说,《疯狂猜成语源码》是一款集教育与娱乐于一体的小程序,它的开发涵盖了Cocos2d-X游戏引擎的使用、...

    元旦谜语之字谜猜猜.doc

    字谜是一种语言游戏,通过巧妙地构造文字和词语,让人们猜测隐藏的答案。这里我们将分析这些字谜中的语言和文字技巧。 1. **谜语解析**: - **白痴**:答案为“呆”,因为“白”字的中心是“口”,“口”在“白”...

    编字谜活动方案(一年级).pdf

    2. 结合课程内容:字谜活动最好能够和当前学习的课程内容相结合,比如学习了哪些汉字,可以设计与之相关的字谜,使学生在游戏中复习和巩固已学知识。 3. 吸引学生兴趣:可以通过一些有趣的形式来吸引学生,比如图片...

Global site tag (gtag.js) - Google Analytics