中等难度，但是需要细心

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

来源，leetcode 每日一题 79. 单词搜索

例如：

  1. board =
  2. [
  3.   ['A','B','C','E'],
  4.   ['S','F','C','S'],
  5.   ['A','D','E','E']
  6. ]
  8. 给定 word = "ABCCED", 返回 true
  9. 给定 word = "SEE", 返回 true
  10. 给定 word = "ABCB", 返回 false

解题思路

  1. 回溯(dfs)
  2. 每次失败回溯的时候，需要重置一下已经遍历过的节点

    代码

    1. class Solution {
    2. public:
    3.  bool exist(vector<vector<char>>& board, string word) {
    4.      bool answer = false;
    5.      int w = board[0].size(), h = board.size();
    6.      vector<vector<int>> attach(h, vector<int>(w));
    7.      for (int i = 0; i < board.size(); i++) {
    8.          for (int j = 0; j < board[0].size(); j++) {
    9.              dfs(board, attach, word, j, i, answer, 0);
    10.              if (answer) {
    11.                  return answer;
    12.              }
    13.          }
    14.      }
    15.      return answer;
    16.  }
    17.  void dfs(vector<vector<char>>& board, vector<vector<int>>& attach, string word, int i, int j, bool& answer, int index) {
    18.      if (board[j][i] != word[index]) {
    19.          return;
    20.      } else if (index == word.length() - 1) {
    21.          answer = true;
    22.          return;
    23.      }
    24.      attach[j][i] = true;
    25.      // 如果相等，探查其周围的情况
    26.      if (j < attach.size() - 1 && attach[j + 1][i] == false) {
    27.          dfs(board, attach, word, i, j + 1, answer, index + 1);
    28.      }
    29.      if (answer) {
    30.          attach[j][i] = false;
    31.          return;
    32.      }
    33.      if (j > 0 && attach[j - 1][i] == false) {
    34.          dfs(board, attach, word, i, j - 1, answer, index + 1);
    35.      }
    36.      if (answer){
    37.          attach[j][i] = false;
    38.          return;
    39.      }
    40.      if (i < attach[j].size() -1 && attach[j][i + 1] == false) {
    41.          dfs(board, attach, word, i + 1, j, answer, index + 1);
    42.      }
    43.      if (answer) {
    44.          attach[j][i] = false;
    45.          return;
    46.      }
    47.      if (i > 0 && attach[j][i - 1] == false) {
    48.          dfs(board, attach, word, i - 1, j, answer, index + 1);
    49.      }
    50.      attach[j][i] = false;
    51.  }
    52. };