निम्नलिखित समस्या दैनिक समाचार पत्र क्रॉसवर्ड का एक उदाहरण है, यहां हमें एक 2-आयामी वर्ण सरणी दी गई है और समस्या कथन 2-आयामी वर्ण सरणी भूलभुलैया से दिए गए शब्द को ढूंढना है। खोज एल्गोरिदम में टॉप-टू-बॉटम, राइट-टू-लेफ्ट और इसके विपरीत से व्यक्तिगत वर्ण ढूंढना शामिल है लेकिन विकर्ण रूप से नहीं।
उदाहरणों से समझते हैं
इनपुट- स्ट्रिंग word-LAYS
2D String[ ] - { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };
आउटपुट- 2D वर्ण सरणी में दी गई स्ट्रिंग की संख्या: 7
व्याख्या - जैसा कि हमें शब्दों की स्ट्रिंग सरणी दी गई है और उनसे, हमें शब्द "LAYS" ढूंढना है जिसे किसी भी दिशा में खोजा जा सकता है जैसे टॉप-बॉटम, राइट-लेफ्ट, बॉटम-टॉप, और लेफ्ट-राइट। कोड में काउंटर फ्लैग हर बार दिए गए खोज स्ट्रिंग के मिलने पर जुड़ जाता है, और अंत में परिणाम के लिए गिनती लौटाई जाती है। उदाहरण में, हम देख सकते हैं कि LAYS 7 बार बना है यानी
1->LOAPYS -LAYS-> लेफ्ट टू राइट
2 ->SAYAOL-LAYS(राइट टू लेफ्ट)
3->LAYSST-LAYS(लेफ्ट टू राइट)
4->MLVAYS-LAYS(लेफ्ट टू राइट)
5->LAYSAA-LAYS(लेफ्ट टू राइट)
6->LAOYLS-LAYS(लेफ्ट टू राइट)
7->(बॉटम टू टॉप) इन रेड LAYS
इनपुट- स्ट्रिंग word- CAMP
2D String[ ] - { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }
आउटपुट- 2D वर्ण सरणी में दी गई स्ट्रिंग की संख्या: 0
व्याख्या-: जैसा कि हमें शब्दों की स्ट्रिंग सरणी दी गई है और उनसे, हमें शब्द "LAYS" ढूंढना है जिसे किसी भी दिशा में खोजा जा सकता है जैसे टॉप-बॉटम, राइट-लेफ्ट, बॉटम-टॉप, और लेफ्ट-राइट। कोड में काउंटर फ्लैग हर बार दिए गए खोज स्ट्रिंग के मिलने पर जुड़ जाता है, और अंत में परिणाम के लिए गिनती लौटाई जाती है। उदाहरण में, हम देख सकते हैं कि BOOK 0 बार बना है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
- हमें एक स्ट्रिंग (word) और स्ट्रिंग सरणी दी गई है जो कुछ उपयोगिता वेरिएबल के साथ 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
