IF-THEN's blog

Recursion, c++
By IF-THEN, history, 5 years ago, In English 
bool dfs(int r, int c) {
    if (r > n || c > m || vis[ndx(r, c)] || grid[ndx(r,c)] == '#') return false;
    if (r == n && c == m) return true;
    if (r!=1 || c!=1) vis[ndx(r, c)] = true;
    return dfs(r+1, c) || dfs(r, c+1);
}

Why Does the previous code terminate once a call is evaluated as true ?

In other words, Why it doesn't mark each reachable cell that does not have "#", as expected ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

ISO C++ Standard (14882:2017) 5.15 para. 1:

The || operator groups left-to-right. The operands are both contextually converted to bool (Clause 4). It returns true if either of its operands is true, and false otherwise. Unlike |, || guarantees left-to-right evaluation; moreover, the second operand is not evaluated if the first operand evaluates to true.

→ Reply