题目

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 =[ ['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

分析

在一个字母矩阵中，寻找单词是否存在。使用深度搜索，四个方向搜索，只要找到一个存在即可，由于一个字母不能使用两次，因此深度搜索时候需要先将其赋值为空，之后再恢复即可。

bool search(char** board, int boardRowSize, int boardColSize, char* word,int p,int q,int index)
{
    //printf("%d %d %d\n",p,q,index);
    if(word[index]=='\0')
        return true;
    else
    {
        if(p>0&&word[index]==board[p-1][q])
        {
            char temp=board[p][q];
            board[p][q]='-';
            if(search(board,boardRowSize,boardColSize,word,p-1,q,index+1)==true)
               return true;
            board[p][q]=temp;
        }
        if(q>0&&word[index]==board[p][q-1])
        {
            char temp=board[p][q];
            board[p][q]='-';
            if(search(board,boardRowSize,boardColSize,word,p,q-1,index+1)==true)
               return true;
            board[p][q]=temp;
        }
        if(p<boardRowSize-1&&word[index]==board[p+1][q])
        {
            char temp=board[p][q];
            board[p][q]='-';
            if(search(board,boardRowSize,boardColSize,word,p+1,q,index+1)==true)
               return true;
            board[p][q]=temp;
        }
        if(q<boardColSize-1&&word[index]==board[p][q+1])
        {
            char temp=board[p][q];
            board[p][q]='-';
            if(search(board,boardRowSize,boardColSize,word,p,q+1,index+1)==true)
               return true;
            board[p][q]=temp;
        }
    }
    return false;
}
bool exist(char** board, int boardRowSize, int boardColSize, char* word) {
    bool answer=false;
    for(int i=0;i<boardRowSize;i++)
    {
        for(int j=0;j<boardColSize;j++)
        {
            if(board[i][j]==word[0])
                answer=search(board,boardRowSize,boardColSize,word,i,j,1);
            if(answer==true)return answer;
        }
    }
    return answer;
}