力扣算法题—079单词搜索【DFS】

青旅半醒 2022-01-06 00:04 270阅读 0赞

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    
    给定 word = "ABCCED", 返回 true.
    给定 word = "SEE", 返回 true.
    给定 word = "ABCB", 返回 false.

1 #include "_000库函数.h"
     2 
     3 //此问题是一个DFS问题，每个单词可以像上下左右四个方向进行下一步行走
     4 
     5 
     6 
     7 class Solution {
     8 public:
     9     bool exist(vector<vector<char>>& board, string word) {
    10         if (board.empty() || board[0].empty())return false;
    11         int m = board.size(), n = board[0].size();
    12         vector<vector<bool>>visted(m, vector<bool>(n, false));//记录是否被访问过
    13         for (int i = 0; i < m; ++i) {
    14             for (int j = 0; j < n; ++j) {
    15                 if (search(board, visted, 0, i, j, word))return true;//每个单词单元都进行上下左右进行搜索！
    16             }
    17         }
    18     }
    19 
    20     bool search(vector<vector<char>>& board, vector<vector<bool>>& visted, int idx, int i, int j, string word) {
    21         if (idx == word.size())return true;
    22         int m = board.size(), n = board[0].size();
    23         if (i < 0 || j < 0 || i >= m || j >= n || visted[i][j] || board[i][j] != word[idx])return false;
    24         visted[i][j] = true;
    25         bool res = (search(board, visted, idx + 1, i - 1, j, word) ||
    26                     search(board, visted, idx + 1, i + 1, j, word) ||
    27                     search(board, visted, idx + 1, i, j - 1, word) ||
    28                     search(board, visted, idx + 1, i, j + 1, word));
    29         visted[i][j] = false;//回溯
    30         return res;
    31     }
    32 };
    33 
    34 void T079() {
    35     Solution s;
    36     vector<vector<char>> board;
    37     string word;
    38     board = { {
        'A', 'B', 'C', 'E'}, {
        'S', 'F', 'C', 'S'}, {
        'A', 'D', 'E', 'E'} };
    39     word = "ABCCED";
    40     cout << s.exist(board, word) << endl;
    41 
    42     
    43 }

转载于:https://www.cnblogs.com/zzw1024/p/10724682.html