Given a 2D board and a word, find if the word exists in the grid.

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

For example,
Given board =

[

  ["ABCE"],

  ["SFCS"],

  ["ADEE"]

]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

头次接触这类题目，对我来说还是有难度的，其实这类题的难点就在于，单纯的DFS，是无法在回溯到某一点的时候去改变该点的状态，因为你无法判断回溯到了哪一点（至少我没有做出来~）。那么用一个for循环，里面是递归这种形式，可以做到的，我想这就是回溯和所谓的DFS的区别吧。

我做过的与该题类似的题目：

Letter Combinations of a Phone Number(带for循环的DFS，组合问题，递归总结)

leedcode：Combinations

　　算法核心：回溯在现实生活中就是一种试探的尝试，例如，你很久以前去过一个地方，只很清楚记得目的地的一个特征（假设到时你能知道），现在你在一个十字路口，不知哪个方向是目的地所在的方向，那就只能选择一个方向进行试探，如果运气不好的话，错了，就只能回到十字路口，在进行下一个方向的尝试，这个回到十字路口就是一种回溯

　　回到该题思路：首先找到头节点，然后开始深搜，深搜的过程需要记录该点是否被纳入到我们的路径中，因为每个点是只能用一次的。

　　错误DFS代码，因为他在回溯的时候无法改变已经访问过的点，如果我们在某一点a[i][j]处，它的上下都能走，但是上只能走一步（也就是说a[i-1][j]的上下左右都是不符合条件的），所以我们在回到a[i][j]处的时候需要把刚刚向上走的那一点(a[i-1][j])的访问状态置回false，因为该点可能在以后成为我们需要再次访问的点，但是现在我们并没有把该点加入到我们的路径中：

class Solution {

private:

  vector<vector<char>> m_board;

  bool visited[][];

  string m_word;

  int max_row;

  int max_col;

public:

  bool dfs(int dep,int i,int j)

  {

    if(i<||i==max_row||j<||j==max_col)

      return false;

    if(m_board[i][j]!=m_word[dep])

      return false;

    if(dep!=m_word.size()-)

      visited[i][j]=true;

    if(visited[i][j]==false&&dep==m_word.size()-)

      return true;

    return dfs(dep+,i-,j)||dfs(dep+,i+,j)||dfs(dep+,i,j-)||dfs(dep+,i,j+);//某一层的上下左右都无路的时候，要把访问标志置回false

  }

  bool exist(vector<vector<char>> &board, string word) {

    //找到起始位置

    m_board=board;

    m_word=word;

    max_row=m_board.size();

    max_col=m_board[].size();

    for (int i=;i<max_row;++i)

    {

      for (int j=;j<max_col;++j)

      {

        if(m_board[i][j]==m_word[]){

          memset(tag,,sizeof(tag));
          visited[i][j]=true;

          if(dfs(,i,j))

            return true;

          else {　　
　　　　　　　　continue;
　　　　　　　　visited[i][j]=false;
　　　　　　　　}

        }

      }

    }

    return false;

  }

};

简单说下我的理解：以前一个点为基础，来搜索它的上下左右，若搜到一点，则一直往下，直到”撞墙“或者不满足条件，就回溯。就是这种走到顶，然后回溯，又走又回溯，直到找到最后的结果。

参考代码：

const int MAX=;

int dire[][]={-,,,,,-,,};

bool visited[MAX][MAX];

class Solution {

private:

    vector<vector<char>> m_board;

    string m_word;

    int max_row;

    int max_col;

    bool res;

public:

    void dfs(int dep,int i,int j)

    {

        if(dep==m_word.size()){

            res=true;

            return;

        }

        for (int q=;q<;++q)

        {

            int newi=dire[q][]+i;

            int newj=dire[q][]+j;

            if(newi>=&&newi<max_row&&newj>=&&newj<max_col&&m_board[newi][newj]==m_word[dep]&&!visited[newi][newj])

            {

                visited[newi][newj]=true;

                dfs(dep+,newi,newj);

                visited[newi][newj]=false;//该位置上下左右都不通

            }

        }

    }

    bool exist(vector<vector<char>> &board, string word) {

        //找到起始位置

        res=false;

        m_board=board;

        m_word=word;

        max_row=m_board.size();

        max_col=m_board[].size();

        for (int i=;i<max_row;++i)

        {

            for (int j=;j<max_col;++j)

            {

                if(m_board[i][j]==m_word[]){

                    memset(visited,,sizeof(visited));

                    visited[i][j]=true;

                    dfs(,i,j);

                    if(res)

                        return true;

                    else{

                        visited[i][j]=false;

                        continue;

                    }

                }

            }

        }

        return false;

    }

};

int main()

{

    freopen("C:\\Users\\Administrator\\Desktop\\a.txt","r",stdin);

    vector<char> a;a.push_back('A');a.push_back('B');a.push_back('C');a.push_back('F');

    vector<char> b;b.push_back('W');b.push_back('G');b.push_back('C');b.push_back('G');

    vector<char> c;c.push_back('B');c.push_back('A');c.push_back('F');c.push_back('Q');

    vector<vector<char>> d;

    d.push_back(a);d.push_back(b);d.push_back(c);

    Solution so;

    cout<<so.exist(d,"ABCCF")<<endl;

    cout<<so.exist(d,"FGQ")<<endl;

    cout<<so.exist(d,"ABCCGQFAG")<<endl;

    return ;

}

巴特西

Word Search（深度搜索DFS，参考）

Letter Combinations of a Phone Number(带for循环的DFS，组合问题，递归总结)

leedcode：Combinations

最新文章

热门文章