leetcode79. 单词搜索

分析

对每个位置进行dfs遍历，每次dfs搜索时向四个方向拓展，如果超出边界或者已经访问过则放弃这个位置，其他情况再次进行dfs遍历，一直到与单词完全匹配时返回true;

typedef pair<int ,int > PII;
class Solution {
public:
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    bool dfs(vector<vector<char>>& board, string word,int x,int y,int cur){
        if(board[x][y]!=word[cur])return false;
        if(cur==word.size()-1)return true;
        char t=board[x][y];
        board[x][y]='.';
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>=board.size()||b<0||b>=board[0].size()||board[a][b]=='.')continue;
            if(dfs(board,word,a,b,cur+1)) return true;;
        }
        board[x][y]=t;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[i].size();j++)
                if(dfs(board,word,i,j,0))return true;
        return false;
        
    }
};