[BackTrack][Medium] 79. Word Search

https://leetcode.com/problems/word-search/description/

 

m x n grid의 문자열이 주어진다. 

이 안에서 특정 word가 존재하는지 여부를 확인하라. 

 

맞는 단어를 하나 하나 확인해 가며 진행한다. 

다만 시작 지점이 모든 영역이다. 

로직 자체는 간단하다.

 

코드 

bool existBT(int idx, vector<bool>& vVisit, vector<vector<char>>& board, string word, int idxW)
{
    int H = board.size();
    int W = board[0].size();
    char target = word[idxW];
    int iy = idx / W;
    int ix = idx % W;
    char cur = board[iy][ix];
    if(vVisit[idx] || target!= cur)
        return false;

    vVisit[idx] = true;
    if(idxW+1 == word.size())
        return true;

    // left 
    if(ix > 0)
    {
        if(existBT(idx-1, vVisit, board, word, idxW+1))
            return true;
    }
    // right
    if(ix < W-1)
    {
        if(existBT(idx+1, vVisit, board, word, idxW+1))
            return true;
    }
    // up
    if(iy > 0)    
    {
        if(existBT(idx-W, vVisit, board, word, idxW+1))
            return true;
    }
    // down
    if(iy < H-1)  
    {   
        if(existBT(idx+W, vVisit, board, word, idxW+1))
            return true;
    }
    vVisit[idx] = false;
    return false;
}


bool exist(vector<vector<char>>& board, string word) 
{        
    vector<bool> vVisit;
    vVisit.resize(board.size()*board[0].size(), false);
    for(int q = 0; q < vVisit.size(); ++q)
    {
        if(existBT(q, vVisit, board, word, 0))
            return true;
    }
    return false;
}

 

 

결과