<p>Given an <code>m x n</code> grid of characters <code>board</code> and a string <code>word</code>, return <code>true</code> <em>if</em> <code>word</code> <em>exists in the grid</em>.</p>

<p>The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word2.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCCED&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;SEE&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/15/word3.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCB&quot;
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n = board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 6</code></li>
	<li><code>1 &lt;= word.length &lt;= 15</code></li>
	<li><code>board</code> and <code>word</code> consists of only lowercase and uppercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you use search pruning to make your solution faster with a larger <code>board</code>?</p>

class Solution {
private:    
    void check(int idx, vector<vector<int>> dp, int row, int rowsize, int col, int colsize, vector<vector<bool>>& visited, bool& ret){
         if(idx < 1 || ret){
           ret = true;
           return;
         }

           int curr = col + 1 < colsize ? dp[idx-1][row*colsize + col + 1]:0;    
           if(curr > 0 && curr != 8 && !visited[row][col]){
             visited[row][col] = true;
             check(idx-1, dp, row, rowsize, col+1, colsize, visited, ret);
             visited[row][col] = false;
           }      
           curr = row+1 < rowsize ? dp[idx-1][(row+1)*colsize + col]:0;   
           if(curr > 0 && curr != 16 && !visited[row][col]){
             visited[row][col] = true;
             check(idx-1, dp, row+1, rowsize, col, colsize, visited, ret);
             visited[row][col] = false;
           }      
           curr = col-1 >= 0 ? dp[idx-1][row*colsize + col - 1]:0;     
           if(curr > 0 && curr != 2 && !visited[row][col]){
             visited[row][col] = true;
             check(idx-1, dp, row, rowsize, col-1, colsize, visited, ret);
             visited[row][col] = false;
           }      
           curr = row-1 >= 0 ? dp[idx-1][(row-1)*colsize + col]:0;   
           if(curr > 0 && curr != 4 && !visited[row][col]){
             visited[row][col] = true;
             check(idx-1, dp, row-1, rowsize, col, colsize,visited, ret);
             visited[row][col] = false;
           }      
           
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
      int rowsize = board.size(), colsize = board[0].size(), wordsize = word.size();
      if(word.size() > rowsize*colsize){
          return false;
      }
      vector<vector<int>> dp(word.size(), vector<int>(rowsize*colsize,0));
      for(int idx = 0; idx < word.size(); idx++){
          cout << "idx:" << idx << endl;
         for(int row = 0; row < rowsize; row++){
            for(int col = 0; col < colsize; col++){
                char currchar = board[row][col];
                bool finded = currchar == word[idx];
                if(idx == 0){
                    dp[idx][row*colsize + col] =  finded; 
                }else{
                        if(!finded)
                           continue;
                        int rightward = col+1 < colsize && dp[idx-1][ row*colsize + col + 1] 
                                                        && dp[idx-1][ row*colsize + col + 1] != 8 ? 2 : 0;
                        
                        int downward = row+1 < rowsize && dp[idx-1][(row+1)*colsize + col] 
                                                       && dp[idx-1][(row+1)*colsize + col] != 16 ? 4 : 0;
    
                        int leftward = col-1 >= 0 &&      dp[idx-1][ row*colsize + col - 1] 
                                                       && dp[idx-1][ row*colsize + col - 1] != 2 ? 8 : 0;
    
                        int upward = row-1 >= 0 &&        dp[idx-1][(row-1)*colsize + col] 
                                                       && dp[idx-1][(row-1)*colsize + col] != 4 ? 16 : 0;
                 
                        vector<vector<bool>> visited(rowsize, vector<bool>(colsize,false));
                        bool passed = false;
                        check(idx, dp, row, rowsize, col, colsize, visited, passed);
                        dp[idx][row*colsize + col] = passed && finded ? downward + rightward + upward + leftward : 0;
                }
                cout << "[" << row << ","<<col<<"]:" << dp[idx][row*colsize + col]<<" ";
                if(dp[word.size()-1][row*colsize + col]){
                   return true;
                }
             }
             cout << endl;
          }
           cout << endl;
      }  
      
      return false;
    }
};
220506