#include <vector>
#include <iostream>

using namespace std;

/**
 * Check if word starts wiht pos exits in board or not
 * @param  board 
 * @param  i    search board from row i
 * @param  j    search board from row j
 * @param  word word to find
 * @param  pos  [description]
 * @return      [description]
 */
bool exist(vector<vector<char> > &board, int i, int j, string &word, int pos)
{
    if (word.size() == pos) return true;
    
    if (i < 0 || board.size() <= i || j < 0 || board[0].size() <= j) return false;
    
    const char c = word[pos];
    if (c != board[i][j]) return false;
    
    board[i][j] = '\0'; // mark the board to indicate the char is used
    
    ++pos;
    bool exists = false;
    if (exist(board, i-1, j, word, pos)
        || exist(board, i, j-1, word, pos)
        || exist(board, i+1, j, word, pos)
        || exist(board, i, j+1, word, pos)
        ) exists = true;
    
    board[i][j] = c; // set back character for backtracing
    return exists;
}


bool exist(vector<vector<char> > &board, string word) 
{
    size_t sizeI = board.size();
    if (sizeI <= 0) return false;
    
    size_t sizeJ = board[0].size();
    
    for (size_t i = 0; i < sizeI; ++i)
    {
        for (size_t j = 0; j < sizeJ; ++j)
        {
            if (exist(board, i, j, word, 0))
                return true;
        }
    }
    
    return false;
}

void stringArrayToVector(string *a, int sizeI, int sizeJ, vector<vector<char> > &vv)
{
    vv.assign(sizeI, vector<char>(sizeJ));
    int vI = vv.size();
    int vJ = vv[0].size();
    for (int i = 0; i < sizeI; ++i)
    {
        for (int j = 0; j < sizeJ; ++j)
        {
            vv[i][j] = a[i][j];
        }
    }
}

int main(int argc, char const *argv[])
{
    string a[] = {
        "ABCE",
        "SFCS",
        "ADEE"
    };
    
    vector<vector<char> > va;
    stringArrayToVector(a, 3, 4, va);
    
    string w = "ABCCED";
    cout << w << (exist(va, w)? "  exists": "  not exist") << endl;
    
    w = "SEE";
    cout << w << (exist(va, w)? "  exists": "  not exist") << endl;
    
    w = "ABCB";
    cout << w << (exist(va, w)? "  exists": "  not exist") << endl;

    return 0;
}