[数据结构与算法]79. 单词搜索

79. 单词搜索

LeetCode刷题打卡第030天 _{（第1篇） 20210808}

题目链接

代码

class Solution {
public:
    vector<int> direction{-1,0,1,0,-1};
    bool exist(vector<vector<char> >& board, string word) {
    //回溯算法里面出的题
    //想到运用深度遍历
        int m = board.size(), n = board[0].size();
        if(m==0||n==0) return false;
        vector<vector<bool>> visited(m, vector<bool>(n));
        bool find=false;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){    
                int w=0;           
                backtracking(board,word,w,i,j,visited,find);        
            }
        }
        return find;
    }
     
    void backtracking(vector<vector<char> >& board,string word,int w,int i,int j, vector<vector<bool>>& visited,bool& find){
        //找出结束条件
        if( i>=board.size() || i<0 || j>=board[0].size()||j<0|| word[w]!=board[i][j] ||visited[i][j]|| find){ 
            return;
        }  
        if(w==word.length()-1){
            find=true;
            return;
        } 
        if(!visited[i][j]){
            visited[i][j]=true;
            for(int m=0;m<4;m++){
                backtracking(board,word,w+1,i+direction[m],j+direction[m+1],visited,find);                     
            }
            visited[i][j]=false;  
        }      
    }
};