79题搜索

class Solution {
public:
    bool check(vector<vector<char>>& board,vector<vector<int>>& temp,string word,int i,int j,int k){
        //若选择起点和字母第一个不相同，则返回false
        if(board[i][j]!=word[k]){
            return false;
        }
        //若对比完所有的字符找到正确的路线，则返回true
        else if(k==word.size()-1){
            return true;
        }
        //对要选择的路线进行标记
        temp[i][j]=true;
        bool result=false;
        //方向
        vector<pair<int,int>>dection{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for(const auto& dec:dection){
            int newi=i+dec.first;
            int newj=j+dec.second;
            if(newi>=0&&newi<board.size()&&newj>=0&&newj<board[0].size()){
                if(!temp[newi][newj]){
                    //如果返回值为true则直接返回true退出循环
                    bool chec=check(board,temp,word,newi,newj,k+1);
                    if(chec){
                        result=true;
                        break;
                    }
                }
            }  
        }
        temp[i][j]=false;//回溯，若所走的路线不符合要求则返回，同时要将之前的true标为false
        return result;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int h=board.size();
        int w=board[0].size();
        vector<vector<int>>temp(h,vector<int>(w));
        //1、找到起点与第一个字母相同的起点
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                bool result=check(board,temp,word,i,j,0);
                if(result){
                    return true;
                }
            }
        }
        return false;
    }
};