Need help with a graph theory question

help
,
1

I am trying to solve Word Search | Practice | GeeksforGeeks problem, its getting wrong answer on a test case that has a very long input so i am not sure what the error is.

Here’s the code

class Solution {
public:
    bool isWordExist(vector<vector<char>>& board, string word) {
        // Code here
        
        int n = board.size();
        int m = board.at(0).size();
    
        vector<vector<int>> visited(n, vector<int>(m, 0));
        
        int xadd[4]={-1, 0, 1, 0};
        int yadd[4]={0, 1, 0, -1};
        int k=0;
        
        queue<pair<int, pair<int, int>>> q;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board.at(i).at(j) == word.at(k)){
                    q.push({k, {i, j}});
                    visited.at(i).at(j) = 1;
                }
            }
        }
        
        if(!q.empty())
            k++;
    
        while(!q.empty()){
            int x = q.front().second.first;
            int y = q.front().second.second;
            q.pop();
            
            for(int i=0; i<4; i++){
                if(x+xadd[i] >= 0 && x+xadd[i] < n && y+yadd[i] >= 0 && y+yadd[i] < m && k < word.size()){
                    if(board.at(x+xadd[i]).at(y+yadd[i]) == word.at(k) && !visited.at(x+xadd[i]).at(y+yadd[i])){
                        q.push({k, {x+xadd[i], y+yadd[i]}});
                        visited.at(x+xadd[i]).at(y+yadd[i]) = 1;
                    }
                }
            }
            
            if(q.front().first == k){
                k++;
            }
        }
        
        return k == word.size();
    }
};
2

Test case on which it fails

2 1

g g

gg

Your output : 0

Expected output : 1

1 Like
3

Thanks