数据结构C++代码实现“找词”游戏是在美国流行的一种游戏,它要求游戏者从一张填满字母的正方形表中,找出包含在一个给定集合中的所有词。这些词可以竖着读(向上或向下)、横着读(从左或从右),或者沿45度对角线斜着读。
时间: 2024-03-17 09:42:24 浏览: 71
好的,以下是一个简单的C++代码实现,用于在输入的字母表中寻找给定的单词列表。
```cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 20;
char table[MAXN][MAXN];
int n, m;
vector<string> words;
bool find_word(string word) {
// 横向查找
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m - word.length(); j++) {
bool flag = true;
for (int k = 0; k < word.length(); k++) {
if (table[i][j + k] != word[k]) {
flag = false;
break;
}
}
if (flag) return true;
}
}
// 竖向查找
for (int i = 0; i <= n - word.length(); i++) {
for (int j = 0; j < m; j++) {
bool flag = true;
for (int k = 0; k < word.length(); k++) {
if (table[i + k][j] != word[k]) {
flag = false;
break;
}
}
if (flag) return true;
}
}
// 斜向查找
for (int i = 0; i <= n - word.length(); i++) {
for (int j = 0; j <= m - word.length(); j++) {
bool flag = true;
for (int k = 0; k < word.length(); k++) {
if (table[i + k][j + k] != word[k]) {
flag = false;
break;
}
}
if (flag) return true;
}
}
return false;
}
int main() {
// 输入字母表
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> table[i][j];
}
}
// 输入单词列表
int num_words;
cin >> num_words;
words.resize(num_words);
for (int i = 0; i < num_words; i++) {
cin >> words[i];
}
// 在字母表中查找单词
for (string word : words) {
if (find_word(word)) {
cout << "Found " << word << "!" << endl;
} else {
cout << "Cannot find " << word << "." << endl;
}
}
return 0;
}
```
在这个实现中,我们首先输入一个 $n\times m$ 的字母表,然后输入一个单词列表。我们使用三个嵌套的循环来遍历字母表,并在每个位置上进行横向、竖向和斜向查找,以确定是否存在一个给定的单词。
阅读全文