Leetcode79 Word Search

记忆点

• 递归
• 引用传递
• 状态还原

思路

特点：每一步都有多个选项，选择一步，又会面临新的选项。
使用递归，注意递归的停止条件，以及递归中传递的变量。目标是找一条路径，所以需要将失败的路线状态还原，避免影响后续查找。

尝试和优化

1. 引用传递状态矩阵 需要记录那些点访问过，如果使用值传递会每次递归重新生产一个实例；
2. 引用传递会将状态传回来，需要将失败的状态手动回滚；
3. 状态矩阵仅需要一个实例，放在循环外避免反复初始化；
4. 取巧的话可以使用现有的矩阵，记录访问过的点。

实现

class Solution {
public:
    bool step(int x, int y, vector<vector<char>>& board, const string& word, int idx) {
        if (idx >= word.length()) return true;
        if (x < 0 || x >= board.size() || y < 0 || y >= board[x].size()) return false;
        if (board[x][y] != word[idx]) return false;

        char ch = board[x][y];
        board[x][y] = '*';
        if (step(x+1, y, board, word, idx+1)) return true;
        if (step(x-1, y, board, word, idx+1)) return true;
        if (step(x, y+1, board, word, idx+1)) return true;
        if (step(x, y-1, board, word, idx+1)) return true;
        board[x][y] = ch;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty()) return true;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (step(i, j, board, word, 0)) return true;
            }
        }
        return false;
    }
};