题解 | #童谣寻找问题#

知识点：

DFS/回溯

分析：

我们使用嵌套的循环遍历整个二维牛群定位系统的每个单元格，然后以每个单元格为起点进行深度优先搜索，判断是否能构建出word。最后，我们按照在单词列表中的顺序对结果进行排序，并返回结果。

遍历二维牛群定位系统的每个单元格：

- 对于每个单元格，以该单元格为起点，分别向上、下、左、右四个方向进行深度优先搜索（DFS）。

- 搜索的路径就是构建的word。

- 在搜索过程中，判断当前构建的word是否在网格中

完整ACcodeC++：

#include <cstring>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型vector<vector<>>
     * @param word string字符串
     * @return bool布尔型
     */
    static const int N = 18;
    int n, m;
    int wn;
    bool dfs(vector<vector<char> >& board, string& word, int i, int j, int idx,
             vector<vector<bool>>& st) {
        if (idx == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.size() || j < 0 || j >=  board[0].size() || st[i][j] ||
                board[i][j] != word[idx]) {
            return false;
        }
        st[i][j] = true;
        if(dfs(board, word, i, j - 1, idx + 1, st) ||
                 dfs(board, word, i, j + 1, idx + 1, st) ||
                 dfs(board, word, i - 1, j, idx + 1, st) ||
                 dfs(board, word, i + 1, j, idx + 1, st)) return true;
        st[i][j] = false;
        return false;
    }
    bool exist(vector<vector<char> >& board, string word) {
        int n = board.size();
        int m = board[0].size();
        int wn = word.length();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vector<vector<bool>> st(n, vector<bool>(m, false));
                if (dfs(board, word, i, j, 0, st)) {
                    return true;
                }
            }
        }
        return false;
    }

//   public:
//     bool exist(vector<vector<char>>& board, string word) {
//         if (board.empty() || board[0].empty()) {
//             return false;
//         }
//         int m = board.size();
//         int n = board[0].size();
//         vector<vector<bool>> visited(m, vector<bool>(n, false));
//         for (int i = 0; i < m; i++) {
//             for (int j = 0; j < n; j++) {
//                 if (backtrack(board, word, i, j, 0, visited)) {
//                     return true;
//                 }
//             }
//         }
//         return false;
//     }

//   private:
//     bool backtrack(vector<vector<char>>& board, string& word, int i, int j,
//                    int index,
//                    vector<vector<bool>>& visited) {
//         if (index == word.size()) {
//             return true;
//         }
//         if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
//                 visited[i][j] || board[i][j] != word[index]) {
//             return false;
//         }
//         visited[i][j] = true;
//         if (backtrack(board, word, - 1, j, index + 1, visited)
//                 || backtrack(board, word, i + 1, j, index + 1, visited)
//                 || backtrack(board, word, i, j - 1, index + 1, visited)
//                 || backtrack(board, word, i, j + 1, index + 1, visited)) {
//             return true;
//         }
//         visited[i][j] = false;
//         return false;
//     }
};