剑指offer 12 寻找矩阵中的字符串序列

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

很明显是一个深度优先搜索, 使用递归的方法.

问题的特殊之处在于, 要保存上一层之前使用过的点. 我的处理方法是这样的: 在进入下一层的时候, 将这个节点内容设置为0(使用temp变量保存原内容). 设置为0是因为字符串序列中不可能出现0(除了结尾). 这样就防止了之后的递归回到此节点. 如果在本次递归中查找失败, 那么就把这个节点的原来内容放回.

可能是因为这个策略, 让内存消耗超过了100%的提交.....

bool search(char** board, int boardSize, int* boardColSize, char* word, int i, int j)
{
    if(*word == 0) return true;
    bool result = false;
    char temp = board[i][j];
    board[i][j] = 0;

    if((i+1<= boardSize-1) && (board[i+1][j] == *word))
    {
        result |= search(board,boardSize, boardColSize, word+1, i+1, j);
    }
    if((i - 1 >= 0) && (board[i - 1][j] == *word))
    {
        result |= search(board,boardSize, boardColSize, word+1, i-1, j);
    }
    if((j - 1 >=0) && (board[i][j - 1] == *word))
    {
        result |= search(board,boardSize, boardColSize, word+1, i, j-1);
    }
    if((j + 1 <= *boardColSize-1) && (board[i][j + 1] == *word))
    {
        result |= search(board,boardSize, boardColSize, word+1, i, j+1);
    }

    if(!result)
    {
        board[i][j] = temp;
    }
    return result;
}



bool exist(char** board, int boardSize, int* boardColSize, char* word){
    if((word == NULL)||(*word==0)) return false;

    bool result = false;
    for(int i = 0; i< boardSize; i++)
    {
        for(int j = 0; j< *boardColSize; j++)
        {
            if(board[i][j] == *word)
            {
                result = search(board,boardSize, boardColSize, word+1, i, j);
                if(result)
                    return true;     
            }
        }
    } 
    return result;
    }