Sword finger offer 12 Path in matrix

The finger of the sword Offer 12. Path in matrix

Medium difficulty 601 Switch to English to receive dynamic feedback
Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false .
The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .

for example , In the following 3×4 The matrix of contains the word “ABCCED”（ The letters in the word are marked ）.

 Example  1：
 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output ：true
 Example  2：
 Input ：board = [["a","b"],["c","d"]], word = "abcd" Output ：false

Tips ：

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• board and word It consists of upper and lower case English letters only
  * Ideas ：
  Imitate the following ideas , Clear up every time .

Ideas

Code

class Solution {
    
public:
    bool flag=0;
    bool dfs(vector<vector<char> >& board, string word,int i,int j,int k){
    
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||board[i][j]!=word[k])
            return 0;
        if(k==word.size()-1)
            return 1;
        // In four directions 
        board[i][j]='\0';
        // prune , no need + It is ||
        bool res=dfs(board,word,i-1,j,k+1)|| dfs(board,word,i+1,j,k+1) || dfs(board,word,i,j-1,k+1) || dfs(board,word,i,j+1,k+1);
        board[i][j]=word[k];
        return res;
    }
    bool exist(vector<vector<char> >& board, string word) {
    
        if(word=="")    return true;

        for(int i=0;i<board.size();i++){
    
            for(int j=0;j<board[0].size();j++){
    
                if(dfs(board,word,i,j,0))
                    return 1;
            }
        }
        return 0;
    }
};