多次递归返回

Question

我正在做leetcode 79 C++解决方案，你需要在二维矩阵中找到单词。我正在用回溯来做到这一点

class Solution {
public:

bool backtrack(int row, int col, int N, vector<vector<char>>& matrix, const string& word, const int num_rows, const int num_cols, const int word_size, bool& result)
    {
        if (word[N]==matrix[row][col])                                                  //Letter in matrix equals current word letter
            {

        if (N==word_size or result)     //BASE CASE: Reached end of word
            return result = true;


                map_been[row][col] = true;    //Cell is used

                if (row!=0 and map_been[row-1][col]==0)}    //Going up
                    backtrack(row-1, col, N+1, matrix, word, num_rows, num_cols, word_size, result);

                if (col!=num_cols and map_been[row][col+1]==0)} //Going right
                    backtrack(row, col+1, N+1, matrix, word, num_rows, num_cols, word_size, result);

                if (row!=num_rows and map_been[row+1][col]==0)} //Going down
                    backtrack(row+1, col, N+1, matrix, word, num_rows, num_cols, word_size, result);

                if (col!=0 and map_been[row][col-1]==0)}    //Going left
                    backtrack(row, col-1, N+1, matrix, word, num_rows, num_cols, word_size-1, result);
            
                map_been[row][col] = false;         //clean-up map

}

        return result;
    }


bool exist(vector<vector<char>>& matrix, string word)
    {
        int num_rows = matrix.size();
        int num_cols = matrix[0].size();
        int word_size = word.size();
        bool result=false;
        vector<vector<bool>> map_been (num_rows, (vector<bool> (num_cols, false)))


        for (int i=0; i<num_rows; i++)
            for (int j=0; j<num_cols; j++)    //starting from every matrix position
            {
                if (backtrack(i, j, 0, matrix, word, num_rows-1, num_cols-1, word_size, result))
                    return true;
            }

        return false;
    }
};

在每个递归步骤中，我有 4 个变体：向上、向左、向右或向下，每个步骤都会产生新的递归。我想知道当我找到整个单词（基本情况）时如何结束所有递归，因为现在当我找到它时，程序会继续向左、向右等计数。

Answer 1

使用递归的结果，一旦成功就返回。
您还可以移动有效性检查以简化流程，并使用参数的大小而不是传递它们。

这里有一个不同的建议：

bool backtrack(int row, 
               int col, 
               int N, 
               const vector<vector<char>>& matrix, 
               const string& word)
{
    return N == word.size() // Found it.
        || ( // Validity checks.
               row >= 0
            && row < matrix.size()
            && col >= 0
            && col < matrix[0].size()
            && N < word.size()
            && word[N] == matrix[row][col]
            // Keep searching.
            && (   backtrack(row-1, col, N+1, matrix, word)
                || backtrack(row, col+1, N+1, matrix, word)
                || backtrack(row+1, col, N+1, matrix, word)
                || backtrack(row, col-1, N+1, matrix, word)));
}