Li Kou 79 word search

Power button 79 Word search

Topic details

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 .

I/o sample

 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 Output ：true

 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
 Output ：true

 Input ：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
 Output ：false

solution ： Backtracking algorithm

       bool exist(vector<vector<char>>&board,string word)
        {
    
            int rLength=board.size();
            int cLength=board[0].size();

            // Create a two-dimensional array , Used to indicate whether the location has been accessed , The array size is the same as board The size of needs to be consistent 
            vector<vector<int>>visitesd(rLength,vector<int>(cLength)); 

            for(int i=0;i<rLength;i++)
            {
    
                for(int j=0;j<cLength;j++)
                {
    
                    // Determine whether it belongs to word search 
                    if(check(board,visitesd,i,j,word,0))
                    {
    
                        return true;
                    }
                }
            }
            return false;
         }

         //k Indicates that the current is word The first character of 
         bool check(vector<vector<char>>&board,vector<vector<int>>&visited,int i,int j,string word,int k)
         {
    
            if(board[i][j]!=word[k])
            {
    
                return false;
            }
            else if(k==word.size()-1)
            {
    
                return true;
            }

            // When word[k] stay board in , But not to the end of the string 
            //1. First set the flag bit to true
            visited[i][j]=true;

            // Create an array of directions , Mark the direction in which you can move 
            vector<pair<int,int>>direction{
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};

            // Whether the same string exists around the tag 
            bool res=false;
            for(auto dir:direction)
            {
    
                //newi,newj  Represents the new coordinate value 
                int newi=i+dir.first;
                int newj=j+dir.second;
                // Judge newi and newj Whether it is beyond the boundary or does not exist 
                if(newi>=0&&newi<board.size()&&newj>=0&&newj<board[0].size())
                {
    
                    // When this value has not been accessed 
                    if(!visited[newi][newj])
                    {
    
                        // Circulation from the inside out 
                        bool flag=check(board,visited,newi,newj,word,k+1);
                        if(flag)
                        {
    
                            // When the next character exists, it will jump out of the loop 
                            res=true;
                            break;
                        }
                    }
                }

            }
            // Reset tag bit 
            visited[i][j]=false;
            return res;

         }