CS106x-Recusion

文章发布时间:

最后更新时间:

文章总字数:
3.4k

预计阅读时间:
13 分钟

作业，文档不长，但是感觉很复杂，不过感觉非常有意思！人机对战哎！

Before Coding

gboggle.h

起手读源码，因为又有图形接口，作业文档反而不是我最先看的，明明lifeGame那会儿一点源码不会读😂

这段代码是一个C++头文件，名为gboggle.h，它定义了一个名为GBoggle的游戏的相关接口和功能。下面是对代码的逐行解释：

  1. 文件开头的注释块提供了文件的基本信息，说明了这个头文件包含的是一个Boggle游戏界面的函数集合，这些函数包括绘制游戏板、管理单词列表和更新计分板。
  2. #ifndef和#define预处理指令用来防止头文件被多次包含进同一个源文件中，这是一种常见的防止重复定义的宏定义方法。
  3. #include <string>和#include "gwindow.h"是包含指令，分别引入了C++标准库中的字符串头文件和另一个名为gwindow.h的头文件，后者可能是一个自定义的图形窗口库。
  4. 定义了两个常量kBoggleWindowWidth和kBoggleWindowHeight，分别代表Boggle游戏窗口的宽度和高度。
  5. 定义了一个枚举类型Player，用来区分人类玩家和电脑玩家。
  6. 函数initGBoggle(GWindow& gw)的声明，该函数用来初始化GBoggle包，并设置使用客户端提供的图形窗口。
  7. 函数shutdownGBoggle()的声明，该函数用来关闭图形窗口并释放与GBoggle包相关联的资源。
  8. 函数drawBoard(int numRows, int numCols)的声明，该函数用来绘制具有指定行数和列数的Boggle游戏板的空布局。
  9. 函数labelCube(int row, int col, char letter)的声明，该函数在指定位置的立方体上绘制一个字母。
  10. 函数highlightCube(int row, int col, bool flag)的声明，该函数根据标志flag的值来高亮或取消高亮指定的立方体。
  11. 函数recordWordForPlayer(const std::string& word, Player player)的声明，该函数记录玩家提交的单词，并更新显示和计分板。单词的得分根据单词的长度来计算。

整个头文件为GBoggle游戏提供了基本的框架和功能声明，具体的实现细节需要在对应的源文件中查看。这个头文件是游戏开发中的一部分，为游戏的界面显示和逻辑处理提供了接口。

懒了，抱一丝儿~
注意，enum Player { HUMAN, COMPUTER };枚举人类与计算机玩家类型，如何使用这个枚举？

1
2
3
4
5
6
7
Player current_player = HUMAN;
Player p1 = HUMAN;
Player p2 = COMPUTER;

if (current_player == HUMAN) {
    // do something
}

WalkThrough

boggle.cpp

main中已经完成了GUI的初始化，只需完成playBoggle();部分。

coding

choose Letter Randomly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 摇晃骰子并展示投掷结果
void chooseLetterRandomly() {
    Vector<string> cube = cubeType;
    for (int i = 0; i < cube.size(); i++) {
        // 洗牌
        int r = randomInteger(i, cube.size()-1);
        string temp = cube[i];
        cube[i] = cube[r];
        cube[r] = temp;
    }

    int d = 4; // dimension
    if (cube.size() % 5 == 0){
        d = 5;
    }

    // 绘制
    int count = 0;
    for (int i = 0; i < cube.size(); i++) {
        if (d == 4 && i % 4 == 0 && i != 0) {
            count = 0;
        } else if (d == 5 && i % 5 == 0 && i != 0) {
            count = 0;
        } else {
            count++;
        }
        for (int j = 0; j < d; j++) {
            int rr = randomInteger(0, 5);
            string letter = cube[count][rr];
            labelCube(count, j, letter);

        }

    }
}

// 找单词并高亮
static void playerFindWord(Player current_player) {
    // do something no matter who is current player

    if (current_player == HUMAN) {

    } else {
        // computer
    }
}

/**
 * Function: playBoggle
 * --------------------
 * Manages all details needed for the user to play one
 * or more games of Boggle.
 */
static void playBoggle() {
    int dimension = getPreferredBoardSize();
    drawBoard(dimension, dimension);
    cout << "This is where you'd play the game of Boggle" << endl;

    /**
     * seem should start at here
     * -------------------------
     * 画版
     * 打乱所有的字符串骰子 Shuffle
     * 递归的找出所有单词containWord（优化大小写
     * 人类回合：输入并计分，空输入表示结束，单词高亮处理
     * 计算机回合：输出所有未被人类发现的单词
     */
    if (dimension == 4) {
        chooseLetterRandomly(kStandardCubes);// kStand全局变量不用传参
    } else {
        chooseLetterRandomly(kBigBoggleCubes);
    }

    Set<string> wordSet = containWords();
    Set<string> visited;

    Player current_player = HUMAN;
    bool flag = true;
    while (flag) {
        string input = getLine("input any possible words, enter [space] to end: "); // 全改成大写
        if (input == " ") {
            current_player = COMPUTER; // HUMAN to COMPUTER
        } else if (wordSet.contains(input) && !visited.contains(input)){
            // 计分，高亮，单词记为以找出
            // 计算机找出所有未被人类找出的单词
        } else {
            cout << "WRONG WORDS! TRY AGAIN:";
        }

        // computer 完成后返回false
        if (current_player == COMPUTER)
            flag =  false;
    }

}

完成递归的课程之后重新写就轻松不少了，顺手达成成就：连续写一百行代码没有bug。

递归部分完成，就是有点小瑕疵，和lifegame那会儿访问越界类似，很好解决，然后顺序完成了搜索单词的工作，应该把？至少搜出来了

仔细检查了一下搜出来的结果，发现搜出了奇怪的单词，面板上并没有，😓，怎么回事捏？

Debug
第一次进入递归时传入了word = “”导致没有访问当前的第一个字母，小问题。
访问过的字母需要设置为visited，如果单词没有成立再撤回
大问题是会搜出不存在的单词，继续De

找到了，传参时将word 赋值为 word + board[i][j + 1] 之类的，并且传入了i，j
作为索引，然鹅i，j没有同步整张，导致每次word都连接了相同的字母；另外，三个方向的递归函数全放在了一起，导致纵向的执行了一次后又去执行向右侧访问的操作，导致非法词汇出现。

解决方案比较简单，在进入递归前确认方向即可，用int flag = 0确认，每次改变方向时+1，用flag的值选择方向。

不需要设置visited集合，因为你不知道用户会选择哪种单词组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void findWordsHelper(Set<string> &allWords, Grid<char> &board, string word, int i, int j, int dimension, int flag, Lexicon &DIC) {

    // base case: 单词正确/访问出界
    if (i + 1 >= dimension || j + 1 >= dimension) {
        flag++; // 改变下轮递归方向
        return;

    } else if (!DIC.containsPrefix(word)) {
        // 剪枝 Lexion containPrefix()
        return;
    } else {
        // rec case
        if (DIC.contains(word)) {
            allWords.add(word);
        }

        // exploer
        // [i][j] visited NO NEED
        // board[i][j]

        if (flag == 0) { // 向右侧递归
            findWordsHelper(allWords, board, word + board[i][j + 1], i, j + 1, dimension, flag, DIC); // i, j 作为单词的下一字母索引同步增加
        } else if (flag == 1) { // 向下
            findWordsHelper(allWords, board, word + board[i + 1][j], i + 1, j, dimension, flag, DIC);
        } else { // 斜向右下
            findWordsHelper(allWords, board, word + board[i + 1][j + 1], i + 1, j + 1, dimension, flag, DIC);
        }


        // unchoose NO NEED
    }
}

void findWords(Set<string> &allWords, Grid<char> &board, string word, int dimension,Lexicon &DIC) {
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            word = board[i][j];
            int flag = 0;
            findWordsHelper(allWords, board, word, i, j, dimension, flag, DIC);
        }
    }
}

// 递归列出单词
Set<string> getAllWords(Grid<char> &board, int dimension, Lexicon &DIC) {
    Set<string> allWords;
    string word = "";
    findWords(allWords, board, word, dimension, DIC);
    return allWords;
}

递归部分完成，剩下的不想做了，躺平……
没办法嘛，时间太少，后面的内容又很好玩，等不及了😋
好像还不太行，看了一下demo，差的太远了，再改改

4月末

以下为7月更新部分

改动一下代码展示风格

我个人不公开代码的另一个原因，是我认为我的代码实现并不那么优秀，虽然能够通过测试，但还是有很多不足，不敢放到大家面前。私底下我们可以对着题目分享思路，可以对着看看各自的实现方式；放到自己的博客上可以介绍自己对题目的理解，实现的技巧，部分代码的摘要；如果别人有疑问，尝试点出或者和他一起解决…

中途做web开发和备考耽搁太长时间，决定推倒重做，阅读start code 发现很多以前忽略的地方，尤其是接口部分。

分析功能，给出以下逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 根据用户选项生成随机词盘，并生成所有可能的词放入词典中 使用新函数
Grid<char> board = initBoard(dimension);
Set<string> words = initWords(board);
Set<string> visited;
// 当玩家为人类时，输入的单词在词典中且为合法新词，则高亮并积分，否则展示对应报错
// 当输入为空时切换玩家为计算机
// 计算机回合直接展示所有(#`O′)未被找出的单词
Player currentP = HUMAN;
while (currentP == HUMAN) {
    string wordinput = getLine("Enter a word: ");
    if (words.contains(wordinput) && !visited.contains(wordinput)) {
        // highlight record visited
        continue;
    } else if (words.contains(wordinput) && visited.contains(wordinput)) {
        // 重复输入
        continue;
    } else if (!words.contains(wordinput) && strlen(wordinput) > 3) {
        // 不存在，错词
        continue;
    } else if (strlen(wordinput) < 4 && strlen(wordinput) > 0) {
        // 长度小于4
        continue;
    } else {
        // 空输入？
        currentP = COMPUTER;
    }
}

使用strlen时注意将string类型转为c语言支持的类型，使用.c_str()方法。
另外，如果右括号左有0会导致编译器（Qt）抽风ecpected token ) got 0。

创建board

1
2
3
4
5
6
7
8
9
10
/**
 * Function: initBoard
 * -------------------
 * 初始化board，设置字符并绘制
 */

static Grid<char> initBoard(int dimension) {
    Grid<char> board(dimension, dimension);
    return board;
}

这种返回值的方法为什么可行？根据大括号来看，board在这个函数结束的时候就已经被销毁了，如何将其传递到主函数？
GIthub copilot：你提到的 board 在函数结束时被销毁的问题是因为 board 是在栈上分配的局部变量。然而，initBoard 函数返回的是一个 Grid 对象的副本，而不是对局部变量的引用。因此，返回的副本在主函数中仍然是有效的。

真的每一步都有坑，给定的骰子是字符串常量，在洗牌前需要将其存入变量中。然后打乱骰子，见上。

递归找出所有单词

接下来就是最关键的初始化词典部分。需要使用递归。找出所有符合的单词。怎么办呢？我们先从一个字符出发：假设一个4乘4的字符格。每一个字符都应该向右寻找，向下寻找，向左下，右下方寻找。并且完成对应的剪枝操作。另外，当一个词成立的时候，还需要将其设置flag。并按照这个flag，使用递归进行高亮。

关键问题来了。怎么实现单词查找呢？先假设一个4x4的网格。然后我的意思是2x2的网格。然后里面的单词分别是”BOOK”。怎么样才能找到这个词呢？我们的递归函数传入这个矩阵。我们从第一个字母开始，它需要去找所有相邻的字母。我大概有思路了，因为我会用回溯法。不断地向左上角去找。当所有的左上角访问完，再访问上。当倒数第二层的左上角的字母都被遍历完以后，退回一级。再访问退回后的那个点的下一个字。
我悟了。单词需要向上不断查找，也需要向右不断查找。不，不对。这样只能查找到与其在同一行、同一列的单词，以及对角线上的单词，不能拐弯。
我又悟了。每一次递归函数都会向当前位置周围的八个方向去访问，这有点像广度优先搜索。不过我们这一次的精髓是深度优先搜索。因为每一次搜索都会向八个方向扩展，并且避免已经访问过的位置。那样的话，所有的可能情况都被覆盖了。是吗？假设是个2x2方格，分别是”BOOK”。B向左访问到O。向左上也访问到O。呃，向左上方访问到C。那这样一来，它只能生成”BO”和”BK”两个词。嗯，就这样。

backtracking

这里插入一些回溯法的练习，不然太懵了，什么都不知道。

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

果然不懂还得回去看课，花半天时间跟着把递归的题练了一手，补习了不少思路。每次递归都向8个方向递归的思路是对的，比如上层是0，本层递归走向为0，1则下一层就有000，001，010，011.就能覆盖所有的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static void initWordsHelper(Lexicon &dic, Set<string> &words, Grid<char> &board, string formed,
                            int i, int j, Grid<int> &visited) {
    for (int ni = -1; ni < 2; ni++) {
        for (int nj = -1; nj < 2; nj++) {
            int x = i + ni, y = j + nj;
            if (x < 0 || x >= board.size() || y < 0 || y >= board.size()) {
                continue;
            }
            if (dic.contains(formed)) {
                words.add(formed);
            } else if (dic.containsPrefix(formed)) {
                continue;
            }

            if (visited[x][y] == 1) {
                continue;
            }
            visited[x][y] = 1;
            initWordsHelper(dic, words, board, formed + board[x][y], i, j, visited);
            visited[x][y] = 0;

        }
    }
}

debug一整天，最后发现控制越界时获取数组宽度的函数调成获取元素总数的了… danm！

参考

最后总算搞明白回溯法递归的实现了，真的抽象。期间查阅了不少视频和文档：
代码随想录-回溯法
CodeStepByStep–backtracking
以及做主要的还是CS106x的lecture7~12，花了半天时间回顾了从最简单的阶乘到n皇后问题。

≡