C++ 检查给定的字符串是否可以由矩阵的相邻单元格中的字符组成

首先，让我们了解矩阵中相邻单元格的含义。为了确定每个组件如何适应您的二维矩阵结构，将每个封闭单元视为由几乎八个相邻元素包围的单元，这些元素位于它们的对角线方向和垂直/水平方向的位置。一个关于格子大小的示例观察是 – 在此设计中，最小的圆形围栏有九个组件。（从左到右和从上到下）单元格[row=9，col=8] – 可以从[row=8，col=7]，[row=10，col=8]等到达，依此类推。这个复杂的连接网络将这些相邻组件链接在一起，它们共享边缘或角落，从而创建定义明确的矩阵结构，提高了其执行多种操作和计算的能力。

方法

• 迭代方法

• 迭代方法II

迭代方法

迭代方法是解决问题的一种策略，涉及执行循环或迭代。例如，可以使用此技术确定是否可以从相邻的矩阵单元格中的字符创建特定字符串。

通常，问题陈述包括目标字符串和字符矩阵。目标是确定是否可以通过在相邻的矩阵单元格之间向上、向下、向左或向右移动来生成目标字符串。

语法

以下是确定是否可以使用相邻的矩阵单元格中的字符创建字符串的语法，假设矩阵表示为2D数组，并且给定字符串保存在名为input String的变量中。

• 将布尔函数string Found设置为false。

• 使用两个嵌套循环遍历矩阵中的所有单元格。

• 对于每个单元格，检查输入字符串中的当前字符是否与矩阵的当前单元格匹配。

• 如果找到匹配，则递归检查输入字符串的剩余字符是否可以使用当前单元格的相邻单元格生成。

• 如果可以使用相邻矩阵单元格生成完整的输入字符串，则将string Found变量更改为true并退出循环。

• 当完成此循环时，如果可以使用矩阵的相邻单元格生成输入字符串，则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.  

步骤

以下是将此策略付诸实践的阶段：

• 第一步 − 从左上角开始遍历矩阵，寻找与当前单元格对应的字符串的初始字符。

• 第二步 − 如果匹配成功，则将当前单元格标记为已访问，并继续下一个字符。

• 第三步 − 如果匹配失败，则继续下一个单元格，并重复第二步。

• 第四步 − 如果无法在任何位置找到字符串下一个字符的匹配项，则返回上一个位置，并尝试另一个相邻单元格。

• 第五步 − 如果能够匹配字符串中的所有字符并达到末尾，则返回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

结论

要确定一个给定的字符串是否可以由矩阵相邻单元格中的字符组成，我们首先必须确定每个元素的相邻单元格。在找到相邻单元格后，我们可以检查字符串中的字符是否与矩阵中每个元素的相邻单元格中的字符匹配。

这种方法在诸如单词搜索谜题或自然语言处理任务等应用中广泛使用，其中我们需要确定给定单词是否可以使用矩阵或网格中相邻的字母构建。如果我们理解矩阵中相邻单元格的概念，我们可以高效地解决这些类型的问题和任务。