好有意思的作业，但是抽象也是真的抽象。

word-Ladder 广度优先搜索

利用广度优先搜索实现在字典中查找单词使起点词到终点词每次只变动一个字母
读源码发现只需完成 generateLadder 函数，传入参数 Lexicon 型 字典常量 english， 起点词与终点词

关于 Lexicon 型变量：
和 Set 型变量有相同的函数接口，

围绕第 0 号找一圈，没有目标，出队，标记已访问；周围一圈每一号再重复，没找到；第二圈再重复，找到，输出每层相连的单词

首先构造函数找到与第 n 个词相似的词，即只有一个字母只差的词。
怎么找？
读 Reader 发现的一种遍历方法：

string word = 'xx';
for (char c0 = 'a'; c0 <= 'z'; c0++){
    word[0] = c0;
    for (char c1 = 'a'; c1 <= 'z'; c1++){
        word[1] = c1;
        if (english.contains(word){
            cout << word << endl;
        }
    }
}

for (string word : english){
    if (word.length() == 2){
        cout << word << endl;
    }
}

写最小测试项目的邻居识别的时候注意到源码中全使用了静态变量，函数，遂查：

static 不导出外部符号，如果你不准备在别的编译单元用，加上 static 就不需要命名得又臭又长来防止冲突了

因为本次作业含 3 个小作业，所以使用静态定义就很方便。

继续找邻居，假设目标是 con -> cot -> bot
~~依次替换第一位为 26 个字母，第二位第三位同理，就有 26~~~~3~~~~ 种情况（！） ~~

屁嘞，不要这样干。遍历字典找和待检测 word 头一致
写了个单词变体，但是调试时发现会漏类型，从 aaa 开始，第一列变量 26 个字母，然后开始遍历第二列，但此时第一列静止了，或许应该单独开一个函数来处理此需求.

暂时不考虑此问题，完成一次入队后，调用该函数自身，传入字典，队首单词，终点单词.

开始修改上述问题:循环结束不更新

//backup
//生成所有单词变体，若字典中有其变体，即加入队列并放入以访问集合
        for (int i = start.length() - 1; i >= 0; i--){
            for (char j = 'a'; j <= 'z'; j++){
                word[i] = j;
                //cout << "try: " << word << endl;
                if (test.contains(word) && !visited.contains(word)){
                    q.enqueue(word);
                    cout << word << " enqueue!" << endl;
                    visited.add(word);
                }
            }
        }

emmmmm……wait a minute 【加粗】

当前词的所有变体好像只需要找有一个字母之差的就 ok 了，我还闷头想怎么从“aaa”遍历到“zzz”，甚至想出来一个”26进制的变形方法“ 【内联代码】
差点算了整整$26 * 26 * 26 = 26^3$【数学公式】

    //生成当前访问词的所有变体 搞不好是递归 将字符串看作是26进制的加法，每次将尾+1个ASCII值，到“z”进位
    //问题：如何判断进位循环语句要执行多少次 当位数<strlen时 

全体目光向我看齐！

然后开始改，不小心忘记引用传递，传进去要变化的结果定义成 const 型，debug 又发现似乎不能调用自身。

想了想，大概是搜索所有的邻居并入队，头出队；每个邻居依次搜索邻居并入队，头出队。

芜湖！！完成

源代码

/**
 * @brief traval
 * @param word
 * @return
 * 查找邻居:查找当前词的所有变体，每次只变一个字母
 */
static void travalCheck(const Lexicon& english, Set<string>& visited, Queue<string>& q, string& word){
    string temp = word;
    int length = word.length();
    for (int n = 0; n < length; n++){

        for (char i = 'a'; i <= 'z'; i++){
            word[n] = i;
            // 【已编辑】 只是一个if语句
        }
        word[n] = temp[n];
    }
}

static void generateLadder(const Lexicon& english, const string& start, const string& end) {
    cout << "Here's where you'll search for a word ladder connecting \"" << start << "\" to \"" << end << "\"." << endl;
    /**
     * BFS
     * TODO 读取start的邻居 con -> cot/kon/ton
     * 先找第一个字母不同的邻居,找到的全放进Set存储
     * 邻居next 先赋start值，循环的改变，有和字典对上就放Set里，直到字典遍历完
     * 没找到目标，上回合的元素出队，next全入队，重复
     * 读取过的邻居设置为已访问-放进Set里
     *
     * 先设置一个小字典进行测试
     * 先在while里面写好在模块化
     */
    Lexicon test = {"con", "cot", "bot", "bat", "bit", "pit", "big", "dig"};
    Set<string> visited;

    Queue<string> q;

    q.enqueue(start);
    visited.add(start);

    //cout << start << " enqueue "<< endl;

    do {
        string word = q.peek();
        if (q.peek() == end){
            cout << q.peek() << endl;
            cout << "Finally finished！" << endl;
            break;
        }

        //生成相邻词并检验入队
        travalCheck(test, visited, q, word);

        //完成一次查找邻居后将第一位出队，避免死循环
        cout << q.dequeue() << " -> ";


    } while (!q.isEmpty());

    /* cout all visited value
    for (string find : visited){
        cout << find << " visited!" << endl;
    }
    */
    return;
}

你先别急，只是完成测试而已，把 test 字典换成 English 进行压力测试，测完发现有点弱智，al -> ak -> at 有冗余行为

继续！读档案发现了新的方法，队列里存的是数组而不是单词！
推倒重写逻辑部分

static void generateLadder(const Lexicon& english, const string& start, const string& end) {
    cout << "Here's where you'll search for a word ladder connecting \"" << start << "\" to \"" << end << "\"." << endl;
    /**
     * BFS
     * TODO 读取start的邻居 con -> cot/kon/ton
     * 先找第一个字母不同的邻居,找到的全放进Set存储
     * 邻居next 先赋start值，循环的改变，有和字典对上就放Set里，直到字典遍历完
     * 没找到目标，上回合的元素出队，next全入队，重复
     * 读取过的邻居设置为已访问-放进Set里
     *
     * 先设置一个小字典进行测试
     * 先在while里面写好在模块化
     *
     * 现在的目标是找到起点到终点的最短路
     * 目前的处境是会输出所有遍历到的单词
     * 读文档发现了重要信息：Queue中存储的是每个单词梯子，而不是简单的单词
     */
    Lexicon test = {"con", "cot", "bot", "bat", "bit", "pit", "pig", "big", "dig"};
    Set<string> visited;

    Queue<string> q;

    q.enqueue(start);
    visited.add(start);

    //cout << start << " enqueue "<< endl;

    do {
        string word = q.peek();
        if (q.peek() == end){
            cout << q.peek() << endl;
            cout << "Finally finished！" << endl;
            break;
        }


        //生成相邻词并检验入队
        travalCheck(test, visited, q, word);

        //完成一次查找邻居后将第一位出队，避免死循环
        cout << q.dequeue() << " -> ";


    } while (!q.isEmpty());

    /* cout all visited value
    for (string find : visited){
        cout << find << " visited!" << endl;
    }
    */
    return;
}

vector 和 SPL 库里的 Vector 是两个类型 ！差点丢大人了

重整思路：

//创建字典实现 con -> cot -> bot -> bit -> pit -> pig
Lexicon test = {"con", "cot", "bot", "bat", "bit", "pit", "pig", "big", "dig"};
//已访问集合
Set<string> visited;

Queue<Vector<string>> q;

Vector<string> ladder = {start};
visited.add(start);
q.enqueue(ladder);
int len = start.length();

do {
    //返回当前ladder长度的函数，假设
    int nowend = ladder.size() - 1;
    Vector<string> check = q.peek();
    if (check[nowend] == end){
        cout << q.peek() << endl;//若数组末位为end，输出
        break;
    }
    //ladder没有完成，弹出队首并更新
    q.dequeue();
    ladder = q.peek();
    //找邻居函数,假设有邻居word
    string tempw = check[nowend];
    string word = tempw;
    for (int i = 0; i < len; i++){
        Vector<string> tempv = ladder;//进行ladder复位
        for (char j = 'a'; j <= 'z'; j++){
            word[i] = j;

            //加一个word形成一个ladder，然后复位，再加另一个word再形成一个ladder，直到全部访问
            if (test.contains(word) && !visited.contains(word)){
                tempv.add(word);
                q.enqueue(tempv);
                break;
            }
        }
        word = tempw;
    }

实现了读取每个 ladder 的末位，检测是否为 end 值，遇到访问空队列 peek 的错误，debug 模式发现 line 22 dequeue 后又访问队首，初次将会报错。

注意暂时未完成返回当前 ladder 长度的函数，随手补上。
开始调试，哎，怎么还是死循环，看一下输出…哎呀，抱一丝，忘记把 word 设置为已访问了【挠头】，补上

再次测试，球进啦！！！！芜湖！！！！起飞！！！！！！

lease enter the source word [return to quit]: con
Please enter the destination word [return to quit]: big
Here's where you'll search for a word ladder connecting "con" to "big".
{"con"}
{"con", "cot"}
{"con", "cot", "bot"}
{"con", "cot", "bot", "bat"}
{"con", "cot", "bot", "bat", "bit"}
{"con", "cot", "bot", "bat", "bit", "pit"}
{"con", "cot", "bot", "bat", "bit", "big"}
{"con", "cot", "bot", "bat", "bit", "big"}

后续将转入大字典进行压力测试。

maze-Generator

耗时良久，至少两周，发现还是不要完全脱离 AI 辅助，否则效率太低。

读源码

maze-types.h

提供了 cell 与 wall 类型可供使用

cell 类接受 int row; int col;
并重载了<运算符: 返回 row1 < row2 或 row1 == row2 && col1 < col2 的真假。

wall 类 含有两个参数 cell one; cell two;
<运算符与 cell 类同理…
wait,看看这里：

inline bool operator<(const wall& one, const wall& two) {
    if (one.one < two.one) return true;
    if (two.one < one.one) return false;
    return one.two < two.two;
} // yes, this is somewhat arbitrary（专横的）, but it can be arbitrary as long as it's consistent

额，return one.two < two.two;是什么意思？
哦，懂了：对 wall1 的 cell2 与 wall2 的 cell2 进行比较， 运算符含义为上文提及的方式。

maze-graphics.h

这里有很多图形接口，但是没有当时看 lifegame 的图形接口时头大了

MazeGeneratorView(); ~MazeGeneratorView(); 展示(~销毁)一个清空（clear）的界面给别的函数功能在此画图
void setDimension(int dimension); 设置迷宫的大小，强制方形
void drawBorder(); 在边界画出界限
void addOneWall(const wall& w); 只是加一堵墙（不是画出来），想展示就调用view.repaint()

下面这个是个大件儿：

/**
 * Method: addAllWalls
 * ----------------
 * Adds (but does not display) all the walls contained within the parameter.
 * To display all newly-added walls on the screen, call view.repaint();
 * Optimized for speed as compared to several sequential calls to addOneWall.
 *
 * This function requires that the parameter passed in is, in fact, a collection
 * that can be iterated through and that contains wall objects.
 */
    template <typename C>
    void addAllWalls(const C& collection) { addAllWalls(collection.begin(), collection.end()); }
    // defined inline as required by template type

• 添加（但不显示）参数中包含的所有墙壁。
• 要在屏幕上显示所有新添加的墙壁，请调用 view.repaint();
• 与依次调用 addOneWall 相比，针对速度进行了优化。
• 此函数要求传入的参数实际上是一个可以迭代且包含墙壁对象的集合。

typename C 意味着可以接受各种类型的 collection，比如说 Set，Vector 之类的

void removeWall(const wall& w);移除数据里的 wall，用repaint()更新画面

void repaint() { GWindow::repaint(); } // inlined for convenience 唯一真神！更新画面

私有变量先不看了。

开展

简单说就是如果两边的房间封闭，就把这堵墙拆掉

额，简单仿照 ifle game 进行了窗口化显示，然后该干嘛？

display

仔细读了读接口文件，试了试把图形画出来，wall 类型在两个 cell 类型中间，为其赋值wall wx {cx1, cy1}; wall wy {cx2, cy2};,再对边界和出入口优化一下，就把左右文档中的图一画出来了。这就折腾了有一阵子，哎 😔

// 初始化房间与墙壁
Set<wall> swall;
for (int i = 0; i < dimension; i++)
{
    for (int j = 0; j < dimension; j++)
    {
        int x = j + 1, y = i + 1;
        if (x > dimension || x < 0 || y > dimension || y < 0)
        {
            continue;
        }
        else
        {
            cell c1{i, j};
            cell c2{i, j + 1};

            cell y1{i, j};
            cell y2{i + 1, j};

            wall w{c1, c2};
            wall wy{y1, y2};
            swall.add(w);  // x方向的墙
            swall.add(wy); // y方向的墙

            // display.addOneWall(wy);
            // display.addOneWall(w);
            // display.repaint();
        }
    }
}

display.addAllWalls(swall);
getLine("press [enter] to continue...");

然后是擦除部分，完全没有思路…
再看看作业文档
问了问 ai，好快的思路！把联通的房间放到一个集合内，两房间不在一个集合就把之间的墙壁删除。

按照与生成墙壁类似的代码结构编写了移除墙壁的代码，仿照 wordladder 进行是否位于集合的检测，大体方向是对了，成功移除了部分墙壁，但是边界没有控制好，因为是随机访问，并不是所有房间都检测过了。

重新看一下代码：while 循环条件为 oneRoom 集合的大小小于房间数，而对房间的访问是随机的，无法保证所有房间在 dimension2 内全部被访问到…不对
擦除的逻辑有问题，重写
重新理解墙壁的生成原理，重读 maze-types.h
x，y 方向相邻两个 cell 之间可以有 wall

怎么还是会在最下和最右边画线啊啊啊啊

你的 if (i + 1 >= dimension || j + 1 >= dimension) continue; 语句会跳过最后一行和最后一列的所有房间，这意味着这些房间不会有任何墙壁。这并不是你想要的结果，你只是想避免在最后一行和最后一列的房间添加右边和下面的墙。
你应该将这个 if 语句应用到添加墙壁的部分，而不是应用到整个循环。

成功绘制正确的起始图

在想擦除墙壁的循环结构时想看看 Set 库有没有 isEmpty 函数，结果猜猜我发现了什么？
shuffle.h!! 让我看看！
哦我的天哪，可以打乱数组，二维数组，集合，字符串。这样就不用自己生成随机数访问了，太棒了。
怎么没有这个库啊，算了，用 CPP 提供的 shuffle 吧

/**
 * 擦除部分
 * 如果两个房间不在同一个集合内，则擦去墙壁
 *
 */
Set<cell> oneRoom;

// 打乱allwall数组，然后一个个遍历两边的房间是否在一个集合内
random_device rd;
mt19937 g(rd());
shuffle(allwall.begin(), allwall.end(), g);

for (int i = 1; i < allwall.size(); i++)
{
    // check if two room
    //ERROR! 可能因为其他墙壁的处理导致被墙分隔的房间都被放进了oneRoom集合内
    if (oneRoom.contains(allwall[i].one) && oneRoom.contains(allwall[i].two)){
        continue;
    } else {
        display.removeWall(allwall[i]);
        oneRoom.add(allwall[i].one);
        oneRoom.add(allwall[i].two);
        display.repaint();
    }
}

getLine("press [enter] to again.");

结果产生了一些逻辑错误
可能因为其他墙壁的处理导致被墙分隔的房间都被放进了 oneRoom 集合内

在迷宫生成中，最小生成树（Minimum Spanning Tree，MST）是一种常用的方法。它可以确保生成的迷宫是完全连通的（即，任意两个房间之间都存在一条路径），并且没有环路（这是迷宫的一个重要特性）。
在你的代码中，你可以使用 Kruskal 算法来生成最小生成树。Kruskal 算法的基本思想是：首先，将所有的墙放入一个列表，并随机打乱这个列表。然后，依次考虑每一堵墙，如果这堵墙两边的房间不在同一个集合中（这可以用并查集来判断），那么就拆除这堵墙，并将两个房间合并到同一个集合中。这样，当所有的墙都被考虑过后，就生成了一个迷宫。
在你的代码中，你已经实现了这个算法的大部分步骤，但是你使用了一个简单的集合 oneRoom 来存储所有已经连接的房间，这并不能正确地处理所有的情况。你应该使用一个并查集来替换这个集合，这样就可以正确地生成迷宫了。

并查集……广搜和深搜也可以，但是会复杂一些
// 3.30 补充了并查集的知识

unionFind

然后一通操作猛如虎，一构建错麻了：什么没有运算方法，无法调用 shuffle 函数，函数名调用错误…
别急别急别急，修好后一运行——访问空数组

/**
 * @brief unionFind 并查集
 * 初始化 每个cell指向其头部，二维数组的索引表示每个cell，存储的内容为其头部
 * 合并   传入两个参数，将其合并：某个索引的cell值改为新的头部
 * 检测   检测两个cell参数的头部是否相同
 *
 */
static Vector<Vector<cell>> initunionFind(int dimension) {
    //初始化二维cell数组，且每个cell的头部为自身
    Vector<Vector<cell>> oneCell;
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            cell c{i, j};
            oneCell[i][j] = c;
        }
    }
    return oneCell;
}

operator ==(cell c1, cell c2) {
    if (c1.row == c2.row && c1.col == c2.col) {
        return true;
    } else {
        return false;
    }
}

static bool test(cell c1, cell c2, Vector<Vector<cell>> oneCell) {
    //cell 类型无法进行==运算，不想重载操作符了。。。最后还是重载了
    return oneCell[c1.row][c1.col] == oneCell[c2.row][c2.col];
}


static void follow(cell boss, cell follower, Vector<Vector<cell>> oneCell) {
    oneCell[follower.row][follower.col] = boss;
}

哦~我大概知道了，初始化 oneCell 的时候我们希望按照二维数组的方式进行，但是 oneCell[i][j]的值其实是 Vector,暂时改成 Grid oneCell(dimension, dimension); 主要是用括号括一下范围，这个 忘记了。

一运行，呃呃，所有的墙都被擦掉了。其实对此有些预感：follow 函数太简单了，不能保证指向头部，想起来了！用 while 循环直到存储的 cell 与索引一致的 findHead 函数！

重整思路：

• 初始化并查集 init
• 检测墙是否将两个房间隔开 test（两个索引内存储的 cell 是否相同 i.e.两 cell 是否有一个 Head）
  • Yes：continue
  • No：拆墙；把 cell 的 Head 统一
    • 起初：每个索引存储其自身
    • 需要合并：将一个的索引存储的内容改为另一个房间 follow

问了问 ai，是在 merge 合并时出了问题：让 c2 从 c1 时会将 c2 与从 c2 的所有子集分隔

嗷嗷嗷！

为了确保 c2 集合的所有元素都指向 c1，我们需要对 merge 函数进行修改。在并查集中，合并两个集合的基本思想是将一个集合的根节点直接指向另一个集合的根节点。在这个过程中，我们需要确保路径压缩被正确应用，以避免形成冗长的链式结构，这样可以提高查询效率。
下面是修改后的 merge 函数，它确保了 c2 集合的所有元素都指向 c1 集合的根节点：

static void merge(cell c1, cell c2, Grid<cell> &oneCell) {
    // 查找c1和c2的根节点
    cell root1 = findHead(c1, oneCell);
    cell root2 = findHead(c2, oneCell);

    // 如果两个节点已经相同，不需要合并
    if (root1 == root2) return;

    // 将root2指向root1，即将c2集合的所有元素指向c1集合的根节点
    oneCell[root2.row][root2.col] = root1;
}

在这个函数中，我们首先找到 c1 和 c2 的根节点，即代表它们所在集合的节点。如果两个根节点已经相同，说明这两个集合已经合并过了，不需要再次合并。如果根节点不同，我们将 c2 的根节点直接指向 c1 的根节点，这样就完成了两个集合的合并。

我的代码oneCell[c2.row][c2.col] = findHead(c1, oneCell);直接修改 c2 的值，而不是 root 的值，进而无法有效变更头部。

done。

/**
 * File: maze-generator.cpp
 * ------------------------
 * Presents an adaptation of Kruskal's algorithm to generate mazes.
 */

#include <iostream>
#include <algorithm>  // for shuffle
#include <random>
using namespace std;

#include "console.h"
#include "simpio.h"

#include "maze-graphics.h" //竟然没预先引用！
#include "maze-types.h"


static int getMazeDimension(string prompt,
                            int minDimension = 7, int maxDimension = 50)
{
    while (true)
    {
        int response = getInteger(prompt);
        if (response == 0)
            return response;
        if (response >= minDimension && response <= maxDimension)
            return response;
        cout << "Please enter a number between "
             << minDimension << " and "
             << maxDimension << ", inclusive." << endl;
    }
}

/**
 * @brief unionFind 并查集
 * 初始化 每个cell指向其头部，二维数组的索引表示每个cell，存储的内容为其头部
 * 合并   传入两个参数，将其合并：某个索引的cell值改为新的头部
 * 检测   检测两个cell参数的头部是否相同
 *
 */
static Grid<cell> initunionFind(int dimension) {
    //初始化二维cell数组，且每个cell的头部为自身
    Grid<cell> oneCell(dimension, dimension);
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            cell c{i, j};
            oneCell[i][j] = c;
        }
    }
    return oneCell;
}

//重载运算符
operator ==(cell c1, cell c2) {
    if (c1.row == c2.row && c1.col == c2.col) {
        return true;
    } else {
        return false;
    }
}


// TODO findHead, 路径压缩
static cell findHead(cell c1, Grid<cell> &oneCell){
    cell top = oneCell[c1.row][c1.col];

    //当索引指向其他cell时
    while (!(top == oneCell[top.row][top.col])) {
        top = oneCell[top.row][top.col];
    }
    //路径压缩
    oneCell[c1.row][c1.col] = top;
    return top;
}

// 同头检测
static bool test(cell c1, cell c2, Grid<cell> &oneCell) {
    //cell 类型无法进行==运算，不想重载操作符了。。。最后还是重载了
    return findHead(c1, oneCell) == findHead(c2, oneCell);
}

// TODO 合并操作 c2从c1
static void merge(cell c1, cell c2, Grid<cell> &oneCell) {

    //oneCell[c2.row][c2.col] = findHead(c1, oneCell);
    cell root1 = findHead(c1, oneCell);
    cell root2 = findHead(c2, oneCell);

    if (root1 == root2){
        return;
    }
    oneCell[root2.row][root2.col] = root1;

}



int main()
{
    while (true)
    {
        int dimension = getMazeDimension("What should the dimension of your maze be [0 to exit]? ");
        if (dimension == 0)
            break;
        cout << "This is where I'd animate the construction of a maze of dimension " << dimension << "." << endl;

        /**
         * i think i should do from here
         * 生成所有的墙壁
         * 擦去起始点的墙壁，随机擦去迷宫内的一堵墙
         * 如果一堵墙分隔了两个房间，把墙擦去
         */

        // 基础显示
        MazeGeneratorView display = MazeGeneratorView(); // 和lifegame题一样的接口调用
        display.setDimension(dimension);
        display.drawBorder();

        // 初始化房间与墙壁
        // 问题：无法避免绘制右，下与边界重合的墙壁 双if判断解决
        Vector<wall> allwall;
        for (int i = 0; i < dimension; i++)
        {
            for (int j = 0; j < dimension; j++)
            {
                if (j + 1 < dimension)
                {
                    cell left{i, j};
                    cell right{i, j + 1};
                    wall horizon{left, right};
                    allwall.add(horizon);
                }

                if (i + 1 < dimension)
                {
                    cell up{i, j};
                    cell down{i + 1, j};
                    wall vertical{up, down};
                    allwall.add(vertical);
                }
            }
        }
        display.addAllWalls(allwall);

        /**
         * 擦除部分
         * 如果两个房间不在同一个集合内，则擦去墙壁
         *
         * 创建并查集
         * 每一个cell是一个子集，每擦除一堵墙，将两个子集合并，直到仅剩一个总集合
         */
        // 打乱allwall数组，然后一个个遍历两边的房间是否在一个集合内
        random_device rd;
        mt19937 g(rd());
        shuffle(allwall.begin(), allwall.end(), g);

        //shuffle(allwall);

        // 初始化并查集
        Grid<cell> oneCell = initunionFind(dimension);

        // 开始擦除！

        for (int i = 0, len = allwall.size(); i < len; i++){
            if (!test(allwall[i].one, allwall[i].two, oneCell)) {
                display.removeWall(allwall[i]);
                display.repaint();
                merge(allwall[i].one, allwall[i].two, oneCell);
            }

        }

        getLine("press [enter] to again.");
        // display.~MazeGeneratorView();
    }

    return 0;
}

时间紧迫，暂时不重构了。
继续看接下来的课，递归是真的怪异，weird。