剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

思路：

深搜需要首先确定搜索的顺序，本道题搜索的顺序是单词word的每一个位置，首先遍历矩阵，如果其中的某一个元素与word的第一个元素相等，我们就去搜索，当搜索到最后一个元素的时候可以确定搜索到的了答案。

同时开辟一个bool数组，因为不能往回搜。

如果下一个位置在范围之内，且没有被使用过，且与word的下一个单词相同，我们才去递归搜索。

代码：

class Solution {
public:
    vector<vector<bool>> st;
    vector<vector<char>> g;
    int dx[4] = {0 ,-1, 0, 1},dy[4] = {1,0,-1,0};

    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size(),m = board[0].size();
        st = vector<vector<bool>> (n + 1, vector<bool> (m + 1));
        g = board;
        //dfs需要先确定搜索顺序
        bool flag = false;
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] == word[0]) if(dfs(i,j,0,word)) flag = true;
            }
        }
        if(flag) return true;
        return false;
    }

    bool dfs(int x,int y,int u,string & word){
        if(u == word.size() - 1) return true;
        st[x][y] = true;
        for(int i = 0; i < 4; i++){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a < g.size() && b >= 0 && b < g[0].size() && !st[a][b] && g[a][b] == word[u + 1]){
                if(dfs(a,b,u + 1,word)) return true;
            }
        }
        st[x][y] = false;
        return false;
    }
};