C++の2D文字配列内の指定された文字列の数のカウント

次の問題は日刊紙のクロスワードの例です。ここでは2次元の文字配列が与えられ、問題のステートメントは2次元の文字配列の迷路から与えられた単語を見つけることです。検索アルゴリズムには、からの個々の文字の検索が含まれます。 上から下へ 、右から左へ 逆もまた同様ですが、斜めではありません。

例を挙げて理解しましょう

入力- 文字列ワード-LAYS

2D文字列[]-{"LOAPYS"、 "KAYSOT"、 "LAYSST"、 "MLVAYS"、 "LAYSAA"、 "LAOYLS"};

出力- 2D文字配列内の指定された文字列の数：7

説明- 単語の文字列配列が与えられているので、それらから、Top-Bottom、Right-Left、Bottom-Top、Left-Rightなどの任意の方向に検索できる単語「LAYS」を見つける必要があります。コード内のカウンターフラグは、指定された検索文字列が見つかるたびに加算され、結果の最後にカウントが返されます。この例では、LAYSが7回形成されていることがわかります。つまり

1-> L O A P YS -LAYS->左から右

2-> S A YA O L -LAYS（右から左）

3-> LAYSS T-LAYS（左から右）

4-> M L V AYS- LAYS（左から右）

5-> LAYSA A-LAYS（左から右）

6-> LA O YLS -LAYS（左から右）

7->（下から上）赤いLAYS

入力- 文字列ワード-CAMP

2D文字列[]-{"BLOOKS"、 "BPOOLK"、 "KOHPKB"、 "BOLKOK"、 "LKIOOB"、 "LAHYBL"}

出力- 2D文字配列内の指定された文字列の数：0

説明-： 単語の文字列配列が与えられているので、それらから、Top-Bottom、Right-Left、Bottom-Top、Left-Rightなどの任意の方向に検索できる単語「LAYS」を見つける必要があります。コード内のカウンターフラグは、指定された検索文字列が見つかるたびに加算され、結果の最後にカウントが返されます。この例では、BOOKが形成されていることがわかります 0 回数。

以下のプログラムで使用されているアプローチは次のとおりです

• String（word）とString配列が提供され、これらはいくつかのユーティリティ変数とともに、さらに処理するためにfindString（）に渡されます。
• 次に、マトリックス内の文字がトラバースされ、文字がピックアップされて文字列が開始されます。
• ピックアップされた文字について、アルゴリズムに従って、指定された文字列を可能なすべての方向に再帰的に検索します。
• 一致するものが見つかった場合、カウンターがインクリメントされます
• 最初の開始文字が完成したら、次の文字に対してこのプロセスが繰り返されます
• 次に、カウントの合計が対応する一致で計算されます
• 次に、最終的な回答が取得され、結果が印刷されます。

例

#include <bits/stdc++.h>
using namespace std;
int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) {
   int count = 0;
   if (r >= 0 && r <= maxR && c >= 0) {
      if (c <= maxC && word[index] == arr[r][c]) {
         char res = word[index];
         index = index + 1;
         arr[r][c] = 0;
         if (word[index] == 0) {
            count = 1;
         } else {
            count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index);
            count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index);
            count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index);
            count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index);
         }
         arr[r][c] = res;
      }
   }
   return count;
}

int findString(string word, int r, int c, string str[], int countR, int countC) {
   int count = 0;
   for (int i = 0; i < countR; ++i) {
      for (int j = 0; j < countC; ++j) {
         count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0);
      }
   }
   return count;
}

int main() {
      string word = "FLOOD";
      string inp[] = {"FPLIOKOD","FLOODYUT","YFLOODPU","FMLOSODT","FILPOYOD", FLOOOODE " };
         string str[(sizeof(inp) / sizeof( * inp))];
         for (int i = 0; i < (sizeof(inp) / sizeof( * inp)); ++i) {
            str[i] = inp[i];
         }
         cout << "Count of number of given string in 2D character array: " << findString(word, 0, 0, str, (sizeof(inp) / sizeof( * inp)), str[0].size());
         return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of number of given string in 2D character array: 6