No.79 单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

解法

这道题目可以使用回溯法来解决,这里提几个关键的地方。
line29 重置为 false,这是回溯法的关键,即将状态回滚回到递归前的状态。
line3 方向数组,配合 line22 可以将代码量压缩很多,而且逻辑关系十分清晰。

class Solution {
public:
    int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
vector<vector<bool>> visited;

bool judge(int x,int y){
    if(x>=0 && y>=0 && y<n && x<m){
        return true;
    }
    return false;
}


bool recursion(const vector<vector<char>>& board,int startx,int starty,const string& word,int index){
    if(index==word.size()-1){
        return word[index]==board[startx][starty];
    }

    if(board[startx][starty]==word[index]){
        visited[startx][starty] = true;
        for(int i=0;i<4;i++){
            int newx = startx+d[i][0];
            int newy = starty+d[i][1];
            if(judge(newx,newy) && !visited[newx][newy] && recursion(board,newx,newy,word,index+1) ){
                return true;
            }
        }
        visited[startx][starty] = false;
    }


    return false;
}

bool exist(vector<vector<char>>& board, string word) {
    m=board.size();
    n=board[0].size();

    visited = vector<vector<bool>>(m,vector<bool>(n,false));

//    if(my==0 ) return false;

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


    return false;
}
};