sundeepblue
3/10/2014 - 2:26 AM

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, w

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board = [ ["ABCE"], ["SFCS"], ["ADEE"] ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

word search in 2d board matrix.cpp
content_copyfile_download
http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html

http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver


solution 1: dfs
solution 2: dfs + trie
solution 3: dp


typedef vector<vector<char>> board;
typedef vector<vector<bool>> flag;

bool is_word_exist_in_board(board &bd, string word) {
    if(word.empty()) return false;
    int m = bd.size(), n = bd[0].size();
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(bd[i][j] == word[0]) {              // gist, compare first letter
                flag visited(m, vector<bool>(n, false));  // in each compare, create a new flag matrix
                if (judge(bd, word, 0, i, j, visited) == true) 
                    return true;
            }
        }
    }
    return false;
}

bool judge(board &bd, string word, int idx, int i, int j, flag &visited) {
    if(!valid(bd, i, j) || visited[i][j] || bd[i][j] != word[idx]) return false; // note the 3rd predicate, note their orders of all 3 predicates
    if(idx == word.size()-1) return true;
    visited[i][j] = true;
    bool found = judge(bd, word, idx+1, i+1, j, visited) 
    ||judge(bd, word, idx+1, i-1, j, visited) 
    ||judge(bd, word, idx+1, i, j+1, visited) 
    || judge(bd, word, idx+1, i, j-1, visited);

    visited[i][j] = false;  // gist, easy to forget!
    return found; // necessary
}

bool valid(board &bd, int i, int j) {
    int m = bd.size(), n = bd[0].size();
    return (0 <= i && i < m && 0 <= j && j < n);
}