C++ 中的单词方块

2025年5月14日 | 阅读 9 分钟

在本文中，我们将使用 C++ 讨论单词方阵方法，包括其语法、参数和示例。

什么是单词方阵？

单词方阵是指一种语言，它由适合在正方形网格内的单词组成。这些单词水平和垂直方向的读法都相同。解决单词方阵的另一个好处是，它不仅能锻炼词汇量，还能提高解决问题的能力。

语法和参数

在深入研究代码之前，让我们先了解一下在 C++ 中创建单词方阵所涉及的基本语法和参数。

语法

它具有以下语法：

参数

words： 一个字符串向量，包含将用于构造单词方阵的单词。

带输出的代码

让我们举一个例子来说明 C++ 中的单词方阵。

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
bool isWordSquare(vector<string>& square) {
    int n = square.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (square[i][j] != square[j][i])
                return false;
        }
    }
    return true;
}
 
void printWordSquare(vector<string>& square) {
    for (const string& s : square) {
        cout << s << endl;
    }
}
 
void backtrack(vector<string>& square, vector<string>& words, int step, vector<vector<string>>& squares) {
    if (step == square.size()) {
        if (isWordSquare(square)) {
            squares.push_back(square);
            printWordSquare(square);
            cout << endl;
        }
        return;
    }
    
    for (const string& word : words) {
        square[step] = word;
        backtrack(square, words, step + 1, squares);
    }
}
 
vector<vector<string>> wordSquares(vector<string>& words) {
    vector<vector<string>> squares;
    int n = words[0].size();
    vector<string> square(n);
    backtrack(square, words, 0, squares);
    return squares;
}
 
int main() {
    vector<string> words = {"ball", "area", "lead", "lady"};
    vector<vector<string>> squares = wordSquares(words);
    return 0;
}
<p><strong>Output:</strong></p>
<div class="codeblock3"><pre>
b a l l
a r e a
l e a d
l a d y
b a l l
a r e a
l e a d
l a d y
</pre></div>
<p><strong>Explanation of Code:</strong></p>
<ul class="points">
<li>In this example, the <strong><em>isWordSquare</em></strong> function checks if the given vector of strings forms a word square or not. It iterates through the square and compares characters at corresponding positions.</li>
<li>Next, <strong><em>printWordSquare</em></strong> is a utility function to print the word square.</li>
<li><strong><em>backtrack</em></strong> is a recursive backtracking function to generate all possible word squares. It fills the square one row at a time, checking if the current configuration forms a word square.</li>
<li><strong><em>wordSquares</em></strong> function initializes the process of generating word squares by calling backtrack.</li>
<li>In the <strong><em>main function</em></strong>, we define a vector of words and call wordSquares function to generate word squares.</li>
</ul>
<h3 class="h3">Example 1:</h3>
<p>Let us take an example to illustrate <strong><em>Word Squares</em></strong> in C++:</p>
<div class="codeblock"><textarea name="code" class="cpp">
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
 
using namespace std;
 
class WordSquareGenerator {
private:
    unordered_map<string, vector<string>> prefixMap;
    vector<string> square;
    int wordLength;
 
    void buildPrefixMap(const vector<string>& words) {
        for (const string& word : words) {
            for (int i = 0; i < wordLength; ++i) {
                string prefix = word.substr(0, i);
                prefixMap[prefix].push_back(word);
            }
        }
    }
 
    bool isPrefixValid(const string& prefix) {
        return prefixMap.find(prefix) != prefixMap.end();
    }
 
    bool backtrack(int step) {
        if (step == wordLength) {
            return true;
        }
 
        string prefix = "";
        for (int i = 0; i < step; ++i) {
            prefix += square[i][step];
        }
 
        if (!isPrefixValid(prefix)) {
            return false;
        }
 
        for (const string& word : prefixMap[prefix]) {
            square[step] = word;
            if (backtrack(step + 1)) {
                return true;
            }
        }
 
        return false;
    }
 
public:
    vector<vector<string>> generateWordSquares(const vector<string>& words) {
        vector<vector<string>> squares;
        if (words.empty()) {
            return squares;
        }
 
        wordLength = words[0].length();
        square.resize(wordLength);
 
        buildPrefixMap(words);
 
        backtrack(0);
 
        squares.push_back(square);
        return squares;
    }
};
 
int main() {
    vector<string> words = {"ball", "area", "lead", "lady"};
    WordSquareGenerator generator;
    vector<vector<string>> squares = generator.generateWordSquares(words);
 
    // Print generated word squares
    for (const auto& square : squares) {
        for (const string& word : square) {
            cout << word << endl;
        }
        cout << endl;
    }
 
    return 0;
}

输出

b a l l
a r e a
l e a d
l a d y

说明

前缀映射： 该算法通过一个 Map 构建，该 Map 对所有单词进行前缀处理，并将其映射到具有相同前缀的单词。此步骤对于查找可以添加以形成单词方阵的单词并满足单词方阵固有的前缀模式至关重要。
回溯： 这个恰如其名的 backtrack 函数被递归地用于一次一行地将单词填充到棋盘上。它通过从方阵先前行中已输入的字母构建前缀来执行此操作，在前缀映射中查找匹配的单词，并解决网格以使其适合。如果使用了匹配的构造器，该函数将停止在新写入的行中写入单词，并开始新的一行。之后，它会回溯并检查其他可能的单词，如果它探索过的单词与当前单词不匹配。
单词方阵生成： 当单词方阵被“完全”填充时（即所有行都已填充单词），当前生成的单词方阵将被添加到 squares 向量中。此工具每个输入单词只创建一个谜题方阵，而不是一组与各自前驱匹配的相同方阵。
输出： 之后，算法会将行和列组合起来以提取单词。最后，将创建的单词方阵打印到控制台。在每一行中，都会从输入中随机选择一个单词。创建单词谜题的列。下面是可以使用输入单词“ball”、“area”、“lead”和“lady”组成的单词方阵的说明。

示例 2

让我们举一个例子来说明 C++ 中的单词方阵。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
 
using namespace std;
 
class WordSquareGenerator {
private:
    unordered_map<string, vector<string>> prefixMap;
    vector<string> square;
    int wordLength;
 
    void buildPrefixMap(const vector<string>& words) {
        for (const string& word : words) {
            for (int i = 0; i < wordLength; ++i) {
                string prefix = word.substr(0, i);
                prefixMap[prefix].push_back(word);
            }
        }
    }
 
    bool isPrefixValid(const string& prefix) {
        return prefixMap.find(prefix) != prefixMap.end();
    }
 
    bool backtrack(int step) {
        if (step == wordLength) {
            return true;
        }
 
        string prefix = "";
        for (int i = 0; i < step; ++i) {
            prefix += square[i][step];
        }
 
        if (!isPrefixValid(prefix)) {
            return false;
        }
 
        for (const string& word : prefixMap[prefix]) {
            square[step] = word;
            if (backtrack(step + 1)) {
                return true;
            }
        }
 
        return false;
    }
 
public:
    vector<vector<string>> generateWordSquares(const vector<string>& words) {
        vector<vector<string>> squares;
        if (words.empty()) {
            return squares;
        }
 
        wordLength = words[0].length();
        square.resize(wordLength);
 
        buildPrefixMap(words);
 
        backtrack(0);
 
        squares.push_back(square);
        return squares;
    }
};
 
int main() {
    vector<string> words = {"wall", "area", "lead", "lane"};
    WordSquareGenerator generator;
    vector<vector<string>> squares = generator.generateWordSquares(words);
 
    // Print generated word squares
    for (const auto& square : squares) {
        for (const string& word : square) {
            cout << word << endl;
        }
        cout << endl;
    }
 
    return 0;
}

输出

w a l l
a r e a
l e a d
l a n e

说明

前缀映射： 代码根据输入单词构建前缀映射。
回溯： backtrack 函数通过考虑与先前填充的字母形成的前缀匹配的可能单词来递归地填充单词方阵。它探索不同的单词组合，直到形成一个有效的单词方阵。
单词方阵生成： 构建单词方阵后，它将被存储在 squares 向量中。
输出： 之后，生成的单词方阵被打印到控制台。每一行代表一个输入单词，列形成单词方阵。在此示例中，输入单词“wall”、“area”、“lead”和“lane”如输出所示，构成了一个有效的单词方阵。

示例 3

让我们再举一个例子来说明 C++ 中的单词方阵。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
 
using namespace std;
 
class WordSquareGenerator {
private:
    unordered_map<string, vector<string>> prefixMap;
    vector<string> square;
    int wordLength;
 
    void buildPrefixMap(const vector<string>& words) {
        for (const string& word : words) {
            for (int i = 0; i < wordLength; ++i) {
                string prefix = word.substr(0, i);
                prefixMap[prefix].push_back(word);
            }
        }
    }
 
    bool isPrefixValid(const string& prefix) {
        return prefixMap.find(prefix) != prefixMap.end();
    }
 
    bool backtrack(int step) {
        if (step == wordLength) {
            return true;
        }
 
        string prefix = "";
        for (int i = 0; i < step; ++i) {
            prefix += square[i][step];
        }
 
        if (!isPrefixValid(prefix)) {
            return false;
        }
 
        for (const string& word : prefixMap[prefix]) {
            square[step] = word;
            if (backtrack(step + 1)) {
                return true;
            }
        }
 
        return false;
    }
 
public:
    vector<vector<string>> generateWordSquares(const vector<string>& words) {
        vector<vector<string>> squares;
        if (words.empty()) {
            return squares;
        }
 
        wordLength = words[0].length();
        square.resize(wordLength);
 
        buildPrefixMap(words);
 
        backtrack(0);
 
        squares.push_back(square);
        return squares;
    }
};
 
int main() {
    vector<string> words = {"eat", "ate", "tea"};
    WordSquareGenerator generator;
    vector<vector<string>> squares = generator.generateWordSquares(words);
 
    // Print generated word squares
    for (const auto& square : squares) {
        for (const string& word : square) {
            cout << word << endl;
        }
        cout << endl;
    }
 
    return 0;
}

输出

e a t
a t e
t e a

说明

在此示例中，我们有一组较小的输入单词：“eat”、“ate”和“tea”。
前缀映射： 代码根据输入单词构建前缀映射。对于每个单词，它会生成所有可能的前缀并将其映射到相应的单词。
回溯： backtrack 函数递归地填充单词方阵。它从一个空方阵开始，并尝试填充每一行，确保已填充字母形成的前缀是有效的。
单词方阵生成： 构建单词方阵后，它将被存储在 squares 向量中。
输出： 最后，生成的单词方阵被打印到控制台。每一行代表一个输入单词，列形成单词方阵。在这种情况下，输入单词“eat”、“ate”和“tea”如输出所示，构成了一个有效的单词方阵。

探索与增强

自定义单词集： 尝试使用您选择的不同单词的单词方阵集合。例如，我们可以使用更长或更短的单词，甚至与特定类别（如动物、植物和国家）相关的单词来重填它们。
优化： 寻找代码优化的可能性，特别是对于具有大量单词的文本。可以使用诸如记忆化和剪枝之类的方法来避免指数级继承，从而使算法更有效。
交互式界面： 设计一个即时界面，让用户可以输入他们自己的单词，并将这些单词即时显示为单词方阵。这可以通过 Qt 或 Flask 等 Web 框架来实现，其中一个必须运行基于 Web 的应用程序。
附加约束： 实施其他可选约束来生成单词方阵，例如词汇的单词长度或方阵内的指定模式。
并行化： 探索并行化策略，通过分配多个线程/进程来提高创建单词方阵的速度。
字典集成： 实现字典 API 或集成字典数据，以根据需要识别用于生成单词方阵的单词。它提供了在运行时使用任何出现的单词的机会，并为用户提供了更多选择，而无需手动编写。
单词方阵求解器： 开发求解函数，该函数在给定包含未完成单词的单词方阵时，返回已完成的单词方阵。为了执行此操作，需要应用某种约束满足系统或启发式搜索。
可视化表示： 使用 OpenCV 或 Matplotlib 库创建图表，从而增强对单词方阵的理解。它允许用户在创建填字游戏时以更具交互性的方式可视化单词方阵的垂直排列。

结论

单词方阵的概念以及使用 C++ 实现它们。单词方阵不仅提供了有趣的编程挑战，还提供了改进解决问题能力的机会。通过理解本文提供的语法、参数和代码实现，读者可以创建自己的单词方阵，并探索解决方案的进一步增强。尝试不同的单词集和优化代码性能是读者可以探索以加深对 C++ 中单词方阵理解的一些方向。

下一主题C++ 中的三法则

C++ 中的单词方块

什么是单词方阵？

语法和参数

带输出的代码

示例 2

示例 3

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的单词方块

什么是单词方阵？

语法和参数

带输出的代码

示例 2

示例 3

结论

相关帖子

C++ 区域分配

C++ 中的 is_fundamental 模板

C++ 中 std::lock_guard 与 std::unique_lock 的区别

C++ Negative_binomial_distribution

在 C++ 中初始化集合的方法

C++ 中查找函数的独占时间

C++ 中的五次斐波那契数

C++ 中的自定义填字游戏

C++ 程序找出独特建筑游戏获胜者

C++ 中的神秘数字

订阅 Tpoint Tech

联系信息

关注我们

教程