亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

題目：

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

 

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

 

例如，在下面的 3×4 的矩陣中包含單詞 "ABCCED"（單詞中的字母已標(biāo)出）。

示例：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

輸出：true

思路：

回溯思想

申明以下遞歸函數(shù)，含義：m*n的board，從位置[i][j]開始，能否找到單詞word，變量visted標(biāo)記找到的字母。

bool check(vector<vector<char>>& board, int m, int n, int i, int j, vector<vector<bool>>& visited, string word)

主函數(shù)中，嘗試每次從舉證不同的位置作為起始位置，調(diào)用上面申明的check函數(shù)，判斷從該位置出發(fā)，能否找到單詞。

代碼：

class Solution {
public:
    vector<int> dir = {-1,0, 1};

    bool valid(int m, int n, int i, int j)
    {
        if(i>=0 && i<m && j>=0 && j<n)
            return true;
        else
            return false;
    }

    bool check(vector<vector<char>>& board, int m, int n, int i, int j,  vector<vector<bool>>& visited, string word)
    { 
        if(board[i][j] != word[0])
            return false;
        
        visited[i][j]=true;
        string s=word.substr(1, word.size()-1);

        if(s.size() == 0 )
            return true;

        for(auto& p: dir)
        {
            for(auto& q: dir)
            {
                if(abs(p)==1 && abs(q)==1)
                    continue;
                
                if(valid(m,n,i+p,j+q) && !visited[i+p][j+q])
                {
                    bool ret = check(board,m,n,i+p,j+q, visited, s);
                    if(ret)
                        return true;
                }
            }
        }

        visited[i][j]=false;
        return false;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0)
            return false;
        
        int m=board.size();
        int n=board[0].size();

        vector<vector<bool>> visited;
        visited.resize(m);
        for(int i=0; i<m; i++)
            visited[i].resize(n);

        
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                bool ret = check(board,m,n,i,j,visited,word);
                if(ret)
                    return true;
            }
        }

        return false;
    }
};