Leetcode 79 Solution

class Solution {
    int m;
    int n;
public:
    bool search(vector<vector<char>>& board, int i, int j, string& word, int k)
    {
        if (k == word.size())
            return true;

        if (board[i][j] != word[k])
            return false;

        if (k == word.size() - 1)
            return true;

        char orig = board[i][j];
        board[i][j] = 0;

        if ((i > 0 && search(board, i - 1, j, word, k + 1))
           || (i < m - 1 && search(board, i + 1, j, word, k + 1))
           || (j > 0 && search(board, i, j - 1, word, k + 1))
           || (j < n - 1 && search(board, i, j + 1, word, k + 1)))
        {
            board[i][j] = orig;
            return true;
        }

        board[i][j] = orig;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        if (word.size() == 0)
            return true;

        m = board.size();
        if (m == 0)
            return false;
        n = board[0].size();

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == word[0])
                {
                    if (search(board, i, j, word, 0))
                        return true;
                }
            }
        }

        return false;
    }
};