Return from multiple recursions

Question

I’m doing leetcode 79 C++ solution, where you need to find word in 2D matrix. I’m doing it with backtracking

class Solution
{
private:
    vector<vector<char>> matrix;            //Пример того как можно создать глобальную переменную чтоб не передавать ее каждый раз в аргументах рекурсивной функции
    string word;

bool backtrack (int row, int col, int N,
                const int num_rows, const int num_cols, const int word_size, vector<vector<bool>>& map_been, bool& result)
    {
        if (word[N]==matrix[row][col])                                                  //Буква в матрице совпала с текущей буквой word
            {
                if (N==word_size or result)                                             //Base case: дошли до конца word
                    return result = true;

                //cout<<"Совпала "<<word[N]<<" N="<<N<<endl;
                map_been[row][col] = true;

                if (!result and col!=num_cols and map_been[row][col+1]==0)              //Идем вправо
                    backtrack(row, col+1, N+1, num_rows, num_cols, word_size, map_been, result);

                if (!result and row!=num_rows and map_been[row+1][col]==0)              //Идем вниз
                    backtrack(row+1, col, N+1, num_rows, num_cols, word_size, map_been, result);

                if (!result and col!=0 and map_been[row][col-1]==0)                     //Идем влево
                    backtrack(row, col-1, N+1, num_rows, num_cols, word_size, map_been, result);

                if (!result and row!=0 and map_been[row-1][col]==0)                     //Идем вверх
                    backtrack(row-1, col, N+1, num_rows, num_cols, word_size, map_been, result);

                map_been[row][col] = false;
            }

        return result;
    }

bool backtrack_v2 (int row, int col, int N, const int num_rows, const int num_cols, const int word_size, vector<vector<bool>>& map_been)
    {
        if (row<0 or row>num_rows or col<0 or col>num_cols or word[N]!=matrix[row][col] or map_been[row][col]==true)
            return false;

        if (N==word_size)                                   //Base case: дошли до конца word
            return true;

        map_been[row][col] = true;
        bool result =  backtrack_v2(row, col+1, N+1, num_rows, num_cols, word_size, map_been)       //Идем вправо
                    or backtrack_v2(row+1, col, N+1, num_rows, num_cols, word_size, map_been)       //Идем вниз
                    or backtrack_v2(row, col-1, N+1, num_rows, num_cols, word_size, map_been)       //Идем влево
                    or backtrack_v2(row-1, col, N+1, num_rows, num_cols, word_size, map_been);      //Идем вверх
        map_been[row][col] = false;

        return result;
    }


public:
bool exist(vector<vector<char>>& matrix, string word)
    {
        int num_rows = matrix.size();
        int num_cols = matrix[0].size();
        int word_size = word.size();
        vector<vector<bool>> map_been (num_rows, (vector<bool> (num_cols, false)));             //Можно еще писать * в саму matrix, чтоб не создавать map_been
        bool result=false;

        this->matrix = matrix;
        this->word = word;

        if (word_size> num_rows*num_cols)
            return false;

        for (int i=0; i<num_rows; i++)
            for (int j=0; j<num_cols; j++)
            {
                //cout<<"i="<<i<<" j="<<j<<endl;

//Первый способ - быстрее выходит из большого количества рекурсий при нахождении word//////////////////////////////////////////

                if (backtrack(i, j, 0, num_rows-1, num_cols-1, word_size-1, map_been, result))
                    return true;

//Второй способ - тоже самое через or (больше рекурсий)////////////////////////////////////////////////////////////////////////
/*
                if (backtrack_v2(i, j, 0, num_rows-1, num_cols-1, word_size-1, map_been))
                    return true;
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
            }

        return false;
    }
};

On every recursion step I have 4 variants: go up, left, right or down, each step makes new recursion. I want to know how to end all of my recursions when I find a whole word (base case), because right now when I find it, the program continues count going left, right etc.

My question is how immediately exit from multiple recursions if I found right answer somewhere deep in one of them.

EDIT: I made 2 variants, 1st was mine, 2nd was suggested by molbdnilo.

But 1st variant works 20% faster (420ms vs 520). My new question is why :)

Answer 1

Use the result of the recursions and return as soon as one is successful.
You can also move the validity checks to simplify the flow, and use the sizes of your arguments instead of passing them.

Here is a different suggestion:

bool backtrack(int row, 
               int col, 
               int N, 
               const vector<vector<char>>& matrix, 
               const string& word,
               vector<vector<bool>>& map_been)
{
    if (row < 0 || row >= matrix.size() || col < 0 || col >= matrix[0].size() || N > word.size()) {
        return false;
    }
    if (N == word.size()) {
        return true;
    }
    map_been[row][col] = true;
    bool result = backtrack(row-1, col, N+1, matrix, word, map_been)
               || backtrack(row, col+1, N+1, matrix, word, map_been)
               || backtrack(row+1, col, N+1, matrix, word, map_been)
               || backtrack(row, col-1, N+1, matrix, word, map_been);
    map_been[row][col] = false;
    return result;