How to pass a 2D array by Reference to a function in C++

Question

How do i pass array b1 in the function dfs, b1 is a 2D integer array used to track whether the node was visited. Sorry for the poor code readability. i want to pass it by reference as it needs to be modified by the function called recursively.Currently getting this error.

Line 33: Char 94: error: 'b1' declared as array of references of type 'int &'
    void dfs(int i,int j,vector<vector<char>>& board,string word,int k,bool& yellow,int& b1[][]){
                                                                                             ^
1 error generated.

class Solution {
public:
    
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        int b1[m][n];
        list<pair<int,int>> mp;
        bool yellow=false;
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]==word[0]){
                    mp.push_front({i,j});
                }
            }
        }
        
        for(auto itr=mp.begin();itr!=mp.end();itr++){
            int i=itr->first;
            int j=itr->second;
            
            dfs(i,j,board,word,0,yellow,b1);
            if(yellow==true){
                
                return yellow;
            }
            memset(b1,0,sizeof(b1));
           
        }
        return yellow;
    }
    void dfs(int i,int j,vector<vector<char>>& board,string word,int k,bool& yellow,int& b1[][]){
        int m = board.size()-1;
        int n = board[0].size()-1;
        b1[i][j]=1;
        if(k==word.size()-1){
            yellow=true;       
        }
        
        if(i+1<=m && board[i+1][j]==word[k+1] &&b1[i+1][j]==0){
            dfs(i+1,j,board,word,k+1,yellow,b1);
        }
        if(i-1>=0 && board[i-1][j]==word[k+1] &&b1[i-1][j]==0){
            dfs(i-1,j,board,word,k+1,yellow,b1);
        }   
        if(j+1<=n && board[i][j+1]==word[k+1]&& b1[i][j+1]==0){
            dfs(i,j+1,board,word,k+1,yellow,b1);
        }
        if(j-1>=0 && board[i][j-1]==word[k+1] && b1[i][j-1]==0){
            dfs(i,j-1,board,word,k+1,yellow,b1);
        }
        
        
    }
};

You cannot have a function signature depending on runtime values of `board`, that is not valid C++. Just use `std::vector` for the board too. — Quimby, May 21 '22 at 11:59
Okay, n-dimensional arrays must have their last n-1 dimensions of known size. Again, use `std::vector`. Furthermore I would not recommend recursive DFS due to possibility of stack overflow. — Quimby, May 21 '22 at 12:38

score 0 · Accepted Answer · answered May 21 '22 at 13:33

Since you already use vector<vector<char>>& board as one parameter, the simplest way to fix this error is to use vector<vector<int>> b1 instead of int b1[m][n].

Please take care of VLAs like int a[n][m], it's not easy to maintain and also not recommended. See more at Why aren't variable-length arrays part of the C++ standard?.

Here is my example to replace your b1 with a 2D vector.

class Solution {
public:

    bool exist(vector<vector<char>> &board, string word) {
        int m = board.size();
        int n = board[0].size();
//        int b1[m][n];
        vector<vector<int>> b1(m, vector<int>(n, 0));

        list<pair<int, int>> mp;

        bool yellow = false;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0]) {
                    mp.push_front({i, j});
                }
            }
        }

        for (auto itr = mp.begin(); itr != mp.end(); itr++) {
            int i = itr->first;
            int j = itr->second;

            dfs(i, j, board, word, 0, yellow, b1);
            if (yellow == true) {

                return yellow;
            }

//            memset(b1, 0, sizeof(b1));
            for (auto &row: b1) {
                std::fill(row.begin(), row.end(), 0);
            }
        }
        return yellow;
    }

//    void dfs(int i,int j,vector<vector<char>>& board,string word,int k,bool& yellow,int& b1[][]){
    void dfs(int i, int j, vector<vector<char>> &board, string word, int k, bool &yellow, vector<vector<int>> &b1) {
        int m = board.size() - 1;
        int n = board[0].size() - 1;
        b1[i][j] = 1;
        if (k == word.size() - 1) {
            yellow = true;
        }

        if (i + 1 <= m && board[i + 1][j] == word[k + 1] && b1[i + 1][j] == 0) {
            dfs(i + 1, j, board, word, k + 1, yellow, b1);
        }
        if (i - 1 >= 0 && board[i - 1][j] == word[k + 1] && b1[i - 1][j] == 0) {
            dfs(i - 1, j, board, word, k + 1, yellow, b1);
        }
        if (j + 1 <= n && board[i][j + 1] == word[k + 1] && b1[i][j + 1] == 0) {
            dfs(i, j + 1, board, word, k + 1, yellow, b1);
        }
        if (j - 1 >= 0 && board[i][j - 1] == word[k + 1] && b1[i][j - 1] == 0) {
            dfs(i, j - 1, board, word, k + 1, yellow, b1);
        }
    }

};

score 0 · Answer 2 · answered May 21 '22 at 14:40

Are you moving from GNU to a more strict C++ compiler?

GNU historically allows passing 2D arrays with run-time variable dimensions. Don't remember the exact syntax, you may need to declare M,N as parameters so that compiler knows where are dimensions coming from.

It's an old FORTRAN trick and there were a lot of requests that C++ should have it as well so GNU did it on it's own (they also have FORTRAN compiler so it was also the matter of interoperability). C99 standard also changed to allow it => C++ is a solitary lame duck now.

If you actually are on GNU, dig around a bit how to declare it but keep in mind that it won't build on other C++ flavors.

Oh and you don't need an array of references to int. Array is always (implicit/hidden) pointer (aka reference). The whole reference frenzy came from arrays being historically "privileged" as pointers accessible without *. Keep in mind that reference is self-dereferencing pointer => you just declared an array of pointers - hidden :-)

When normal references are declared in the same scope with their usage compiler knows how to optimize out the hidden pointer aspect but if you cross a function call boundary they have to go as pointers. If you hide them in array compiler has to give up - but it has full right to scream since array of references is conceptual nonsense and you wouldn't be to initialize them => they would all be null bombs if compiler would allow them.

NB: In C++20 you can "reassign" a reference but not explicitly - only as a part of a larger object's self-mut(il)ation (don't try at home :-).

How to pass a 2D array by Reference to a function in C++

2 Answers2