关于记忆化搜索问题的请教（leetcode 79.单词搜索）

[siriussilen]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        bool ans = false;
        int n = board.size();
        int m = board[0].size();
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                check(board, word, ans, i, j, 0);
            }
        }
        return ans;
    }
    void check(vector<vector<char>>& board, string word, bool &ans, int i, int j, int index) {
        if(ans || word[index] != board[i][j]) return;
        if(index == word.length() - 1 && word[index] == board[i][j]) {
            ans = true;
            return;
        }
        int n = board.size();
        int m = board[0].size();
        
        board[i][j] <<= 2; //保证节点不走回头路
        if(i > 0) check(board, word, ans, i - 1, j, index + 1);
        if(i < n - 1) check(board, word, ans, i + 1, j, index + 1);
        if(j > 0) check(board, word, ans, i, j - 1, index + 1);
        if(j < m - 1) check(board, word, ans, i, j + 1, index + 1);
        board[i][j] >>= 2; //把该点还原回去
            
    }
};

https://i.imgur.com/A0eWxd2.png

上图说明：既然我使用了记忆还原"board[i][j] >>=2"那么在每次 for 循环的时候 board 数组应该都是还原正常的，但是我 debug 的时候发现并没有还原

我想请教一下各位，对于我注释的那条代码是怎么理解的，我想让它确保递归的时候不走回头路（保证["a","a"], "aaa"的这种情况不会出现），但是我在 Debug 的时候发现并没有我预期的那样，请问除了引入一个记忆数组以外，用这种“回溯” 应该如何修改我的代码呢？

[potcode99]

char 类型，8bit。字符'Z'用整数 90 表示，位移两位溢出了吧？丢失了位信息，所以还原不了了

[siriussilen]

@potcode99 您说的的确是一个问题，但是我刚刚实验的时候发现问题应该不是在这里

[siriussilen]

@potcode99 收回我上面的话，我把
board[i][j] <<= 2;
改为
board[1][j] += 128;
就好啦 看来的确是这里的问题！
谢谢啦！

[aneureka]

看了你的帖子，我就顺便去做了哈哈