-1

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?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Janhavi Patil.
  • 1
  • 1
  • 1
    The first one may be checking an out of bounds element, or one in a previous row. Always do a bound check before accessing – Mad Physicist Aug 07 '22 at 06:32
  • This seems like a good time to learn how to [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your programs. For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through your code statement by statement, while monitoring variables and their values. – Some programmer dude Aug 07 '22 at 06:33
  • 2
    Though the root problem, in my not very humble opinion, is that you attempt to use a so-called "competition" or "judge" site to learn C++. Such sites are ***not*** any kind of learning or teaching resource, no matter what you might have been told. All they seem to teach are bad habits, bad code, and often also invalid code. If you really want to learn C++ then invest in [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282). There's no good substitute for that, except college and university. – Some programmer dude Aug 07 '22 at 06:35

1 Answers1

2

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.

john
  • 85,011
  • 4
  • 57
  • 81