这道题之前一直没敢做，没想到前天用递归一遍过了。

。

当时为什么想着用递归，而不是dp呢。由于我想到达某个位置的情况有非常多，即使从当前位置開始的搜索是已知的，但之前的状态是如何的也无从得知啊，实话实说，我是不会用dp解这个。。

递归的思路就好说多了，从当前点開始。有上下左右四个位置能够探測，假设探測成功的话，要把当前的位置用其它符号标记出来，以免反复訪问。实际上就是DFS嘛。仅仅只是入口多一些。

须要注意的一点是，每一个点都能够作为起点。所以这个要穷举一下。否则会漏掉情况的。

当然有一种情况走通就能够返回了。剪枝之。

代码又臭又长，只是work：

class Solution {

public:

    int row, column;

    bool doexist(vector<vector<char> > &board, string &word, int len, int i, int j){

        if(len == word.length())    return true;

        bool res;

        if(i>0&&board[i-1][j] == word[len]){

            board[i-1][j] = '.';

            res = doexist(board, word, len+1, i-1, j);

            if(res) return true;

            else    board[i-1][j] = word[len];

        }

        if(i<row-1&&board[i+1][j] == word[len]){

            board[i+1][j] = '.';

            res = doexist(board, word, len+1, i+1, j);

            if(res) return true;

            else    board[i+1][j] = word[len];

        }

        if(j>0&&board[i][j-1] == word[len]){

            board[i][j-1] = '.';

            res = doexist(board, word, len+1, i, j-1);

            if(res) return true;

            else    board[i][j-1] = word[len];

        }

        if(j<column-1&&board[i][j+1] == word[len]){

            board[i][j+1] = '.';

            res = doexist(board, word, len+1, i, j+1);

            if(res) return true;

            else    board[i][j+1] = word[len];

        }

        return false;

    }

    bool exist(vector<vector<char> > &board, string word) {

        row = board.size();

        if(row == 0)    return false;

        column = board[0].size();

        char c;

        for(int i=0;i<row;i++){

            for(int j=0;j<column;j++){

                if(board[i][j] == word[0]){

                    board[i][j] = '.';

                    if(doexist(board, word, 1, i, j))

                        return true;

                    board[i][j] = word[0];

                }

            }

        }

        return false;

    }

};