Interview Question |Flood Fill Problem| Recursion & DFS| C++

5 min readNov 25, 2023

Interview Question |Flood Fill Problem| Recursion & DFS| C++

Code :

class Solution {
   const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
   const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

   bool search(vector<vector<char>> &grid, string &word, int i, int j, int n, int m) {
       if (grid[i][j] != word[0]) return false;
       for (int dir = 0; dir < 8; dir++) {
           int x = i + dx[dir], y = j + dy[dir];
           int index;
           for (index = 1; index < word.size(); index++) {
               if (x < 0 || y < 0 || x >= n || y >= m || grid[x][y] != word[index]) break;
               x += dx[dir];
               y += dy[dir];
           }
           if (index == word.size()) return true;
       }
       return false;
   }

English :

This C++ code defines a class named Solution that contains a method called search. This method takes a 2D vector grid representing a character grid, a string word to search for, and the indices (i, j) representing the starting position in the grid. The method returns a boolean indicating whether the word can be found starting from the given position and moving in any of the eight possible directions (horizontal, vertical, and diagonal).

Let’s break down the code:

The class Solution has two private arrays dx and dy, each containing eight elements. These arrays represent the changes in the x and y directions for the eight possible moves (up, down, left, right, and diagonals).
The search method checks if the character at the current position (i, j) in the grid is equal to the first character of the target word. If not, it immediately returns false.
It then iterates over the eight possible directions using a loop. For each direction, it checks if the characters in the grid, starting from the current position and moving in that direction, match the characters in the target word.
The loop is terminated if any of the following conditions are met:

The index goes beyond the boundaries of the grid (x < 0, y < 0, x >= n, y >= m).
The character in the grid at the current position does not match the corresponding character in the target word.

If the loop completes successfully (i.e., the index reaches the size of the word), it means that the entire word has been found in the specified direction. In this case, the method returns true.
If none of the directions result in finding the entire word, the method returns false.

This code is a part of a larger algorithm, possibly for solving a word search problem where you need to find if a given word exists in a 2D grid of characters. The recursion is implicit in the way the problem is being solved by exploring all possible directions from the current position.

Hindi :

यह C++ कोड एक “Solution” नामक वर्ग को परिभाषित करता है जिसमें “search” नामक एक विधि होती है। इस विधि में 2D वेक्टर “grid” होता है जो एक वर्ण ग्रिड को प्रतिष्ठित करता है, एक स्ट्रिंग “word” होती है जिसे खोजना है, और इंडिस (i, j) जो ग्रिड में शुरुआती स्थान को प्रतिष्ठित करते हैं। इस विधि ने यह सुनिश्चित करने के लिए बनाई है कि शब्द दिए गए स्थान से शुरू होकर किसी भी आठ संभावित दिशा में मिल सकता है (क्षैतिज, लंबवत, और कोने में)।

चलिए कोड को खोलते हैं:

“Solution” वर्ग के पास दो निजी एरे “dx” और “dy” हैं, प्रत्येक में आठ तत्व होते हैं। ये एरे आठ संभावित चालों के लिए x और y दिशाओं में परिवर्तनों को दर्शाते हैं (ऊपर, नीचे, बाएं, दाएं, और कोनों में)।
“search” विधि यह जांचती है कि ग्रिड में वर्तमान स्थान (i, j) पर वर्ण क्या लक्षित शब्द के पहले वर्ण से मेल खाता है या नहीं। अगर नहीं, तो वह तुरंत false लौटाती है।
फिर यह एक लूप का उपयोग करके आठ संभावित दिशाओं पर यात्रा करती है। प्रत्येक दिशा के लिए, यह जांचती है कि ग्रिड में, वर्तमान स्थान से शुरू होकर उस दिशा में चलने से क्या वर्ण लक्षित शब्द के वर्णों से मेल खाता है।
लूप को समाप्त किया जाता है अगर निम्नलिखित में से कोई भी स्थिति पूरी होती है:

इंडेक्स ग्रिड की सीमा से पार जाता है (x < 0, y < 0, x >= n, y >= m)।
ग्रिड में वर्तमान स्थान पर वर्ण लक्षित शब्द के संबंधित वर्ण से मेल नहीं खाता है।

यदि लूप सफलतापूर्वक पूरा होता है (अर्थात इंडेक्स शब्द के आकार तक पहुंचता है), तो इसका अर्थ है कि इसे संबंधित दिशा में पूरा शब्द मिल गया है। इस स्थिति में, विधि true लौटाती है।
यदि किसी भी दिशा में पूरा शब्द नहीं मिलता है, तो विधि false लौटाती है।

यह कोड शायद एक बड़ी एल्गोरिदम का हिस्सा है, संभावना है कि एक शब्द खोज समस्या का हल करने के लिए है जहां आपको यह निर्धारित करना है कि क्या दिए गए शब्द को वर्ण ग्रिड में पाया जा सकता है या नहीं। रिकर्सन इस स्थिति को हल करने के तरीके में समाहित है।

Hinglish :

Ye C++ code ek class Solution ko define karta hai jisme ek method search shamil hai. Ye method ek 2D vector grid ko lekar aata hai jo ek character grid ko represent karta hai, sath hi ek string word jo dhoondhna hai, aur indices (i, j) jo grid mein shuruaati sthiti ko darshata hai. Ye method ek boolean return karta hai jo yeh batata hai ki kya shabd diye gaye sthiti se shuru hokar kisi bhi of aath dishaon mein paya ja sakta hai (horizontal, vertical, aur diagonal).

Chaliye is code ko todte hain:

Class Solution ke paas do private arrays hain - dx aur dy, jinme har ek mein aath elements hain. Ye arrays grid mein chale jane wale aath sambhavit kriyaaon (upar, neeche, left, right, aur diagonal) ko darshate hain.
search method yeh check karta hai ki kya grid mein di gayi sthiti (i, j) par sthit akshar hamare target shabd ke pehle akshar ke barabar hai ya nahi. Agar nahi, toh ye turant false return karta hai.
Fir ye aath sambhavit dishaon par loop chalata hai. Har ek disha ke liye, ye check karta hai ki kya grid mein, vartaman sthiti se shuru hokar us disha mein chalne par, shabd ke aksharon ka saath diye gaye shabd ke aksharon ke saath match hota hai ya nahi.
Loop ko tab roka jata hai agar kisi bhi yeh shart puri ho:

Index grid ke seemaon se bahar jata hai (x < 0, y < 0, x >= n, y >= m).
Grid mein vartaman sthiti par akshar shabd ke corresponding akshar ke saath match nahi karta hai.

Agar loop safalta pura hota hai (yaani, index shabd ke size tak pahunch jata hai), toh yeh iska matlab hai ki poori word di gayi disha mein payi gayi hai. Is case mein, method true return karta hai.
Agar koi bhi disha poori word ko nahi milati, toh method false return karta hai.

Ye code shayad kisi bada algorithm ka hissa hai, shayad kisi word search samasya ko hal karne ke liye jahan aapko yeh dhoondhna hai ki kya ek diya gaya word ek 2D grid mein maujood hai ya nahi. Recursion isme implicit taur par istemal hoti hai taki vartaman sthiti se sabhi sambhavit dishaon ko explore kiya ja sake.

Question Link :

https://www.geeksforgeeks.org/problems/flood-fill-algorithm1856/1?page=1&category=Recursion&sprint=94ade6723438d94ecf0c00c3937dad55&sortBy=submissions