数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究检查给定字符串是否可以使用矩阵相邻单元格的字符构成
让我们首先了解矩阵中相邻单元格的含义。为了确定每个组件如何在您的二维矩阵结构中拟合，请将每个封闭单元可视化为被几乎八个相邻元素包围，这些元素位于它们周围/来自它们的对角方向以及垂直/水平方向。关于晶格大小可以进行一个示例观察 - 此设计中最小的圆形封闭体包含九个组件。（从左到右和从上到下）单元格 [行=9，列=8] - 在 [行=8，列=7] 的范围内，…[行=10，列=8]，等等。这个复杂的连接网络连接了这些相邻的组件，它们共享边或角；创建了一个定义良好的矩阵结构，提高了其执行各种操作和计算的能力。
方法
迭代方法
迭代方法 II
迭代方法
迭代方法是一种解决问题的策略，它涉及执行循环或迭代。例如，此技术可用于确定是否可以从相邻矩阵单元格中的字符创建特定字符串。
通常，问题陈述包括目标字符串和字符矩阵。目标是确定是否可以通过在相邻矩阵单元格之间向上、向下、向左或向右移动来生成目标字符串。
语法
确定是否可以使用相邻矩阵单元格中的字符创建字符串的语法，假设矩阵表示为二维数组，并且给定字符串保存在名为 input String 的变量中。
将布尔函数 string Found 设置为 false。
使用两个嵌套循环遍历矩阵中的所有单元格。
对于每个单元格，检查 input string 中当前字符是否与矩阵的当前单元格匹配。
如果找到匹配项，则递归检查是否可以使用当前单元格在矩阵中的相邻单元格生成 input string 中剩余的字符。
如果可以使用附近的矩阵单元格生成完整的 input string，则将 string Found 变量更改为 true 并退出循环。
完成此循环后，如果可以使用矩阵的相邻单元格生成 input string，则 string Found 返回 true，否则返回 false。
算法
步骤 1 - 将布尔变量“found”的值更改为 false。
步骤 2 - 单独查看每个矩阵单元格。
步骤 3 - 如果所需字符串的第一个字符与当前单元格匹配，我们使用当前单元格的点和字符串中下一个字符的索引来执行递归函数“search”。
步骤 4 - 在返回之前，如果“search”函数的索引等于所需字符串的长度，则必须将“found”变量设置为 true。
步骤 5 - 我们通过循环遍历它们来检查相邻单元格中的字符。如果其中任何一个与字符串的下一个字符匹配，则使用更高的索引和新的坐标再次执行“search”方法。
步骤 6 - 如果没有相邻单元格与字符串中的下一个字符匹配，则退出函数。
示例 1
can_form_string 方法迭代地确定是否可以从指定的单元格 (i,j) 开始使用相邻矩阵单元格生成提供的字符串。如果可以使用相邻单元格创建整个字符串，则返回 true；否则，返回 false。
要测试的字符串被硬编码为“abcfi”，并且在主函数中为矩阵中的每个单元格调用 can_form_string 函数。如果找到匹配项，则应用程序会生成一条消息，指示可以使用相邻矩阵单元格构造该字符串。如果无法使用相邻矩阵单元格创建该字符串，则会生成一条此类消息。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 3;
char matrix[N][N] = {
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'}
};
bool can_form_string(int i, int j, const char* str) {
if (*str == '\0') {
return true;
}
if (i < 0 || i >= N || j < 0 || j >= N) {
return false;
}
if (matrix[i][j] != *str) {
return false;
}
const char* rest_of_str = str + 1;
return (
can_form_string(i-1, j, rest_of_str) ||
can_form_string(i+1, j, rest_of_str) ||
can_form_string(i, j-1, rest_of_str) ||
can_form_string(i, j+1, rest_of_str)
);
}
int main() {
const char* str_to_check = "abcfi";
bool result = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
result = can_form_string(i, j, str_to_check);
if (result) {
break;
}
}
if (result) {
break;
}
}
if (result) {
cout << "The string "" << str_to_check << "" can be formed using adjacent cells of the matrix." << endl;
} else {
cout << "The string "" << str_to_check << "" cannot be formed using adjacent cells of the matrix." << endl;
}
return 0;
}
输出
The string << str_to_check << can be formed using adjacent cells of the matrix.
算法
以下是将此策略付诸实践的步骤 -
步骤 1 - 从左上角开始导航矩阵，查找与当前单元格对应的字符串的第一个字符。
步骤 2 - 如果匹配，则将当前单元格标记为已访问并转到字符串的下一个字符。
步骤 3 - 如果不匹配，我们继续下一个单元格并再次重复步骤 2。
步骤 4 - 如果我们在任何时候都无法找到字符串中下一个字符的匹配项，则返回到上一个位置并尝试另一个相邻单元格。
步骤 5 - 如果我们能够匹配字符串中的所有字符并到达字符串的末尾，则返回 true。否则返回 false。
示例 2
此应用程序中的 canFormString() 函数迭代地确定是否可以从相邻矩阵单元格的字符中构成提供的字符串。
该过程接收一个字符串、一个矩阵、字符串中当前字符的索引、当前行和列索引、一个用于已访问单元格的监控矩阵以及一个已访问单元格索引的矩阵。如果函数成功创建了字符串，则返回 true；如果它无效，则返回 false。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool canFormString(vector<vector<char>>& matrix, string s, int i, int j, int k,
vector<vector<bool>>& visited) {
if (k == s.length())
return true;
if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size() ||
visited[i][j] || matrix[i][j] != s[k])
return false;
visited[i][j] = true;
bool canForm = canFormString(matrix, s, i - 1, j - 1, k + 1, visited) ||
canFormString(matrix, s, i - 1, j, k + 1, visited) ||
canFormString(matrix, s, i - 1, j + 1, k + 1, visited) ||
canFormString(matrix, s, i, j - 1, k + 1, visited) ||
canFormString(matrix, s, i, j + 1, k + 1, visited) ||
canFormString(matrix, s, i + 1, j - 1, k + 1, visited) ||
canFormString(matrix, s, i + 1, j, k + 1, visited) ||
canFormString(matrix, s, i + 1, j + 1, k + 1, visited);
visited[i][j] = false;
return canForm;
}
int main() {
vector<vector<char>> matrix{{'A', 'C', 'P'},
{'A', 'O', 'E'},
{'G', 'B', 'L'}};
string s1 = "APPLE";
string s2 = "BALL";
string s3 = "GOOGLE";
vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
cout << s1 << " can " << (canFormString(matrix, s1, 0, 0, 0, visited) ? "" : "not ") << "be formed\n";
cout << s2 << " can " << (canFormString(matrix, s2, 0, 0, 0, visited) ? "" : "not ") << "be formed\n";
cout << s3 << " can " << (canFormString(matrix, s3, 0, 0, 0, visited) ? "" : "not ") << "be formed\n";
return 0;
}
输出
APPLE can not be formed BALL can not be formed GOOGLE can not be formed
结论
要查看是否可以使用矩阵的相邻单元格中的字符创建给定字符串，我们必须首先找到每个元素的相邻单元格。一旦我们找到了相邻单元格，我们就可以检查字符串中的字符是否与矩阵中每个元素的相邻单元格中的字符匹配。
此方法广泛用于诸如单词搜索谜题或自然语言处理任务之类的应用程序中，在这些应用程序中，我们需要确定是否可以使用矩阵或网格中相邻的字母构造给定的单词。如果我们理解矩阵中相邻单元格的概念，我们可以有效地解决这些类型的问题和任务。
137 次查看
