79. 单词搜索

题目链接

解题思路

• 一道回溯的题目。
• 我现在在[i, j]，然后处理到单词的index位置，index之前的都已经解决了，现在要往哪走？很明显如果[i + 1, j]的位置等于index的单词，我可以去「试试」能不能走通。所以其实很简单，每当来到[i, j]，单词index，我就看上下左右四个位置，如果和index的位置相等，就可以去试试。如果上下左右都不行，那就说明「此路不通」，这一次的尝试失败了。
• 有一个细节，我怎么能够「不走回头路」？很简单，我走过的位置，就把其变成一个不可能的字母，比如255。

代码

class Solution {
public:

    vector<vector<int>> dir{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    // 当前在[i, j]   来到了单词的index位置
    bool process(vector<vector<char>>& board, string &word, int index, int i, int j, const int n, const int m) {
        if (index == word.size()) {
            return true;
        }
        // 这个for循环其实就是上下左右四个方向尝试
        for (int k = 0; k < 4; ++k) {
            int next_i = i + dir[k][0];
            int next_j = j + dir[k][1];
            bool ans = false;
            if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m && board[next_i][next_j] == word[index]) {
                board[next_i][next_j] = 250;    // 标记我已经走过了
                ans = process(board, word, index + 1, next_i, next_j, n, m);
                board[next_i][next_j] = word[index];   // 不要忘记恢复回来
            }
            if (ans) {
                return true;
            }
        }
        return false;

    }

    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                bool ans = false;
                if (board[i][j] == word[0]) {
                    board[i][j] = 250;
                    ans = process(board, word, 1, i, j, n, m);
                    board[i][j] = word[0];
                }
                if (ans) {
                    return true;
                }
            }
        }
        return false;
    }
};