If condition evaluates to false on changing the sequence of conditions. (C++)

Question

I am trying to solve the "Find Number of Islands in a 2D matrix" problem and I am using DFS technique to count the number of adjacent 1's in the matrix.

In the dfs() function, the condition - if( (arr[i][j]=='0') || i<0 || j<0 || i==r || j==c) evaluates to false when (arr[i][j] == '0') condition is written first in sequence but when written like this - if(i<0 || j<0 || i==r || j==c || (arr[i][j]=='0')) it evaluates to true.

This condition is used to check whether the current values of i and j are not out of bounds and that the element arr[i][j] of the matrix is not equal to '0'.

The code:

class Solution {
public:
    void dfs(vector<vector<char>>& arr, int i, int j, int& r, int& c){
        if( (arr[i][j]=='0') || i<0 || j<0 || i==r || j==c)
            return;
        // MARKED VISITED
        arr[i][j] = '0';
        dfs(arr,i,j+1,r,c);
        dfs(arr,i,j-1,r,c);
        dfs(arr,i+1,j,r,c);
        dfs(arr,i-1,j,r,c);
    }
    
    int numIslands(vector<vector<char>>& arr) {
        int rows=arr.size();
        if(rows==0){return 0;}
        int cols=arr[0].size();

        int numOfIslands=0;
        int i=0;
        int j=0;
        int r=arr.size();
        int c=arr[0].size();
        for( i=0;i<r;i++){
            for( j=0;j<c;j++){
                if(arr[i][j]=='1'){
                    dfs(arr, i , j,r,c);
                    numOfIslands++;
                }
            }
        }

        return numOfIslands;
    }
};

This code works only when the element in the matrix is '1' but terminates when element '0' is encountered. Will someone please explain the reason for the failure of the if condition?

Answer 1

Operator || (and similarly operator &&) are always evaluated left to right, and evaluation stops when the result is known. So if the left hand side of || is true then the right hand side is not evaluated. This is known as short circuit evaluation.

So suppose that i equals -1 in this expression

(arr[i][j]=='0') || i<0 || j<0 || i==r || j==c

then you access arr[-1][j] and that is an out of bounds array access which means your program has undefined behaviour, so the expression could evaluate to anything, or could even crash.

But in this expression

i<0 || j<0 || i==r || j==c || (arr[i][j]=='0')

i<0 evaluates to true, so the whole expression is true, and the remaining clauses of the expression are unevaluated. So you avoid the undefined behaviour of the first version and you get the correct result of true.