در این مطلب، روش نوشتن برنامه جستجوی کلمه در یک شبکه دو بعدی از کاراکترها بیان شده و برنامه آن در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «سی‌شارپ» (#C) پیاده‌سازی شده است. یک شبکه دو بعدی ( ۲D Grid) از کلمات داده شده است؛ هدف، پیدا کردن تمام وقوع‌های یک کلمه در شبکه است. یک کلمه می‌تواند با کلمه موجود در هر ۸ جهت تطبیق پیدا کند. اگر همه کاراکترهای کلمه در یک جهت تطبیق پیدا کنند، گفته می‌شود که کلمه در آن جهت یافت شده است (نه در شکل زیگ‌زاگ). همچنین، شایان ذکر است که این مسئله، یکی از پرسش‌هایی است که در مصاحبه‌های استخدامی مایکروسافت مطرح می‌شود.

برای درک بهتر مطلب، مثال زیر قابل توجه است. 

Input:  grid[][] = {"GEEKSFORGEEKS",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "GEEKS"

Output: pattern found at 0, 0
        pattern found at 0, 8
        pattern found at 1, 0

Input:  grid[][] = {"GEEKSFORGEEKS",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "EEE"

Output: pattern found at 0, 2
        pattern found at 0, 10
        pattern found at 2, 2
        pattern found at 2, 12

نمودار  زیر یک شبکه بزرگ‌تر و وجود کلمات مختلف در آن را نشان می‌دهد.

ایده‌ای که در اینجا مورد استفاده قرار گرفته، ساده است. همه سلول‌ها چک می‌شود، اگر سلول اولین کاراکتر کلمه را داشت، یکی یکی، همه جهت‌ها از جهت تطابق کلمه مورد بررسی قرار می‌گیرند. در ادامه، پیاده‌سازی این رویکرد انجام شده است.

پیاده‌سازی در ++C

// C++ programs to search a word in a 2D grid 
#include<bits/stdc++.h> 
using namespace std; 
  
// Rows and columns in given grid 
#define R 3 
#define C 14 
  
// For searching in all 8 direction 
int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; 
int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; 
  
// This function searches in all 8-direction from point 
// (row, col) in grid[][] 
bool search2D(char grid[R][C], int row, int col, string word) 
{ 
    // If first character of word doesn't match with 
    // given starting point in grid. 
    if (grid[row][col] != word[0]) 
      return false; 
  
    int len = word.length(); 
  
    // Search word in all 8 directions starting from (row,col) 
    for (int dir = 0; dir < 8; dir++) 
    { 
        // Initialize starting point for current direction 
        int k, rd = row + x[dir], cd = col + y[dir]; 
  
        // First character is already checked, match remaining 
        // characters 
        for (k = 1; k < len; k++) 
        { 
            // If out of bound break 
            if (rd >= R || rd < 0 || cd >= C || cd < 0) 
                break; 
  
            // If not matched,  break 
            if (grid[rd][cd] != word[k]) 
                break; 
  
            //  Moving in particular direction 
            rd += x[dir], cd += y[dir]; 
        } 
  
        // If all character matched, then value of must 
        // be equal to length of word 
        if (k == len) 
            return true; 
    } 
    return false; 
} 
  
//  Searches given word in a given matrix in all 8 directions 
void patternSearch(char grid[R][C], string word) 
{ 
    // Consider every point as starting point and search 
    // given word 
    for (int row = 0; row < R; row++) 
       for (int col = 0; col < C; col++) 
          if (search2D(grid, row, col, word)) 
             cout << "pattern found at " << row << ", "
                  << col << endl; 
} 
  
// Driver program 
int main() 
{ 
    char grid[R][C] = {"GEEKSFORGEEKS", 
                       "GEEKSQUIZGEEK", 
                       "IDEQAPRACTICE"
                      }; 
  
    patternSearch(grid, "GEEKS"); 
    cout << endl;  
    patternSearch(grid, "EEE"); 
    return 0; 
}

پیاده‌سازی در جاوا

// Java program to search a word in a 2D grid 
import java.io.*; 
import java.util.*; 
  
class GFG  
{ 
  
    // Rows and columns in given grid 
    static int R, C; 
  
    // For searching in all 8 direction  
    static int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 };  
    static int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 };  
  
    // This function searches in all 8-direction from point  
    // (row, col) in grid[][]  
    static boolean search2D(char[][] grid, int row, 
                            int col, String word) 
    { 
            // If first character of word doesn't match with  
            // given starting point in grid.  
            if (grid[row][col] != word.charAt(0)) 
                return false; 
  
            int len = word.length(); 
              
            // Search word in all 8 directions 
            // starting from (row,col) 
            for (int dir = 0; dir < 8; dir++) 
            { 
                // Initialize starting point 
                // for current direction  
                int k, rd = row + x[dir], cd = col + y[dir]; 
  
                // First character is already checked,  
                //  match remaining characters 
                for (k = 1; k < len; k++) 
                { 
                    // If out of bound break  
                    if (rd >= R || rd < 0 || cd >= C || cd < 0) 
                        break; 
  
                    // If not matched, break  
                    if (grid[rd][cd] != word.charAt(k)) 
                        break; 
  
                    // Moving in particular direction  
                    rd += x[dir]; 
                    cd += y[dir]; 
                }  
  
                // If all character matched, then value of must  
                // be equal to length of word 
                if (k == len) 
                    return true;  
            } 
        return false; 
    } 
  
    // Searches given word in a given 
    // matrix in all 8 directions 
    static void patternSearch(char[][] grid, String word) 
    { 
            // Consider every point as starting  
            // point and search given word  
            for (int row = 0; row < R; row++)  
            { 
                for (int col = 0; col < C; col++)  
                { 
                    if (search2D(grid, row, col, word)) 
                        System.out.println("pattern found at " + row +  
                                                            ", " + col); 
                } 
            } 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
            R = 3; 
            C = 13; 
            char[][] grid = {{'G','E','E','K','S','F','O','R','G','E','E','K','S'}, 
                                {'G','E','E','K','S','Q','U','I','Z','G','E','E','K'}, 
                                {'I','D','E','Q','A','P','R','A','C','T','I','C','E'}}; 
            patternSearch(grid, "GEEKS"); 
            System.out.println(); 
            patternSearch(grid, "EEE"); 
    } 
}  
  
// This code is contributed by rachana soma

پیاده‌سازی در سی‌شارپ

// C# program to search a word in a 2D grid  
using System; 
class GFG  
{ 
  
    // Rows and columns in given grid  
    static int R, C; 
  
    // For searching in all 8 direction  
    static int[] x = {-1, -1, -1, 0, 0, 1, 1, 1}; 
    static int[] y = {-1, 0, 1, -1, 1, -1, 0, 1}; 
  
    // This function searches in all 8-direction  
    // from point (row, col) in grid[,]  
    static bool search2D(char[,] grid, int row, 
                         int col, String word)  
    { 
        // If first character of word doesn't match  
        // with given starting point in grid.  
        if (grid[row,col] != word[0]) 
        { 
            return false; 
        } 
  
        int len = word.Length; 
  
        // Search word in all 8 directions  
        // starting from (row,col)  
        for (int dir = 0; dir < 8; dir++)  
        { 
            // Initialize starting point  
            // for current direction  
            int k, rd = row + x[dir], cd = col + y[dir]; 
  
            // First character is already checked,  
            // match remaining characters  
            for (k = 1; k < len; k++)  
            { 
                // If out of bound break  
                if (rd >= R || rd < 0 || cd >= C || cd < 0) 
                { 
                    break; 
                } 
  
                // If not matched, break  
                if (grid[rd, cd] != word[k]) 
                { 
                    break; 
                } 
  
                // Moving in particular direction  
                rd += x[dir]; 
                cd += y[dir]; 
            } 
  
            // If all character matched, then value of k 
            // must be equal to length of word  
            if (k == len)  
            { 
                return true; 
            } 
        } 
        return false; 
    } 
  
    // Searches given word in a given  
    // matrix in all 8 directions  
    static void patternSearch(char[,] grid,  
                              String word) 
    { 
        // Consider every point as starting  
        // point and search given word  
        for (int row = 0; row < R; row++) 
        { 
            for (int col = 0; col < C; col++) 
            { 
                if (search2D(grid, row, col, word)) 
                { 
                    Console.WriteLine("pattern found at " +  
                                         row + ", " + col); 
                } 
            } 
        } 
    } 
  
    // Driver code  
    public static void Main(String []args)  
    { 
        R = 3; 
        C = 13; 
        char[,] grid = {{'G', 'E', 'E', 'K', 'S', 'F', 'O', 
                         'R', 'G', 'E', 'E', 'K', 'S'}, 
                        {'G', 'E', 'E', 'K', 'S', 'Q', 'U',  
                         'I', 'Z', 'G', 'E', 'E', 'K'}, 
                        {'I', 'D', 'E', 'Q', 'A', 'P', 'R',  
                         'A', 'C', 'T', 'I', 'C', 'E'}}; 
        patternSearch(grid, "GEEKS"); 
        Console.WriteLine(); 
        patternSearch(grid, "EEE"); 
    } 
}  
  
// This code is contributed by Rajput-Ji

خروجی قطعه کدهای بالا به صورت زیر است.

pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0

pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

منبع [+]