Function receiving different value than passed

Question

I wrote a simple code for DFS using C++, but the value that I am passing and the value that the function is receiving are different. Printing the values received by the function explains.

Can you please help me out?

#include <bits/stdc++.h>

using namespace std;

void dfs(int i, int j);
char graph[51][51];
int n, m, loop = 0, inx, iny, completed = 0;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int i, j, k, a, b, c;
  cin >> n >> m;

  for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
      cin >> graph[i][j];
    }
  }

  for (i = 1; i <= n, completed == 0; i++) {
    for (j = 1; j <= m, completed == 0; j++) {
      inx = i;
      iny = j;
      dfs(i, j);
    }
  }

  if (completed == 1)
    cout << "YES\n";
  else
    cout << "NO\n";

  return 0;
}

void dfs(int i, int j) {
  cout << i << " " << j << "\n"; // for checking values taken by the function

  if (completed)
    return;

  if (i == inx && j == iny) {
    if (loop >= 4)
      completed = 1;
    return;
  }

  // loop will increase exponentially !!!!!!
  int k = loop;
  if (j < m && graph[i][j] == graph[i][j + 1]) {
    loop++;
    dfs(i, j + 1);
  }

  loop = k;
  if (j > 1 && graph[i][j] == graph[i][j - 1]) {
    loop++;
    dfs(i, j - 1);
  }

  loop = k;
  if (i > 1 && graph[i][j] == graph[i - 1][j]) {
    loop++;
    dfs(i - 1, j);
  }

  loop = k;
  if (i < n && graph[i][j] == graph[i + 1][j]) {
    loop++;
    dfs(i + 1, j);
  }
}

In case anyone is interested, I was trying this question.

(OT: [*Why should I not #include ?*](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)) — Biffen, Dec 13 '18 at 08:08
well , that doesn't explain why this dfs function is accepting weired garbage values .... — harshraj22, Dec 13 '18 at 08:11
More on-topic: https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — Biffen, Dec 13 '18 at 08:13
warning in for instance "for(i=1;i<=n,completed==0;i++)" the result of "i<=n" is lost. "a,b" and "a&&b" are not the same things. You have several times that error — bruno, Dec 13 '18 at 08:15
OT: You are having bad indices: in C++, indices are zero-based, so `int array[7]` will have valid indices [0..6]. It should *not* be a problem unless user inputs 51 for either m or n (by the way: strange array size, usually, one uses powers of 2), as you'd then access `graph[51][x]` or `graph[x][51]`, which would both be out of range, but you are wasting memory (first row and colunm will always be unused). — Aconcagua, Dec 13 '18 at 08:50
Assume the following simple 1x3 matrix: `{ { A, A, A } } As your recursive calls check for start value only (`i == inx`) due to the order of your checks, you'd then visit: (0, 0), (0, 1), (1, 1), (0, 1), (0, 0) and happily detect a circle where none is. You need to prevent re-visiting already visited notes, e. g. by marking them as such. By the way: as soon as you hit an already visited node again (unless it was the direct predecessor), you found a loop - no matter if it was the starting point of your DFS or not... — Aconcagua, Dec 13 '18 at 08:54
yes , I know that the solution is wrong . I figuered it out , but the problem is with dfs function accepting diffrent value than provided . ps. I have just started to learn graph theory for competative programming . regarding 51, the constraints of the question won't allow m or n to be 51 or larger . — harshraj22, Dec 13 '18 at 08:59
*'accepting different value than provided'* apart from specific multithreaded scenarios (another thread invalidly overwriting current one's stack), I never ever saw that happening in 15 years of professional SW development. But you write out in any recursive call, and it might be easy to mix up the outputs. You might try indenting according to call depth, that will give you a better image of what's happening. — Aconcagua, Dec 13 '18 at 09:21
please don't scare me with these high level terms . use simple ways to explain to newbies like me . — harshraj22, Dec 13 '18 at 09:24
`class CallDepthGuard { static inline unsigned int depth = 0; public: CallDepthGuard() { ++depth; } ~CallDepthGuard() { --depth; } unsigned int get() { return depth; } }; void dfs(/*...*/) { CallDepthGuard g; for(unsigned int i = 0; i < g.get(); ++i) std::cout << ' '; std::cout << i << ' ' << j << std::endl; /* ... */ }` - this will indent each pair of i/j one space more for each recursive call one level down the stack - those not indented at all are those called from main function directly. You'd then see more clearly what's going on. — Aconcagua, Dec 13 '18 at 09:30
By the way, is there any specific reason for dropping synchronisation between streams (`sync(false), tie(0)`)? Usually, that's totally unnecessary... — Aconcagua, Dec 13 '18 at 09:49
Just noticing: `inx = i; iny = j; dfs(i, j); void dfs(int i, int j) { if (i == inx && j == iny) { return; } }`, i. e. you won't ever encounter any recursive call anyway... — Aconcagua, Dec 13 '18 at 09:52
Cannot reproduce with my shortened variant: `int main(int argc, char* argv[]) { memset(graph, 0, sizeof(graph)); n = m = 4; for (int i = 1; i <= n && completed == 0; i++) { // ...` - output is absolutely as expected (1, 1), (1, 2), ... — Aconcagua, Dec 13 '18 at 09:55
regarding tie(0) , I just know that it makes code faster. (obiously , its useful only in competative programming as this might have drawbacks ) . and if you care about correctness of code , I corrected it and submitted it long time ago , you may check [link](https://codeforces.com/problemset/submission/510/46963293) here . but still , your suggestions are welcome . — harshraj22, Dec 13 '18 at 13:07

score 1 · Accepted Answer · edited Dec 13 '18 at 08:18

1

At least part of the problem is that you are not understanding how operators work in C++.

for(i=1;i<=n,completed==0;i++){

The expression i<=n,completed==0 has the effect of evaluating i <= n, discarding the result, then evaluating completed == 0, and giving the result of that.

So the end condition of the loop is essentially completed == 0. The relationship between i and n does not affect execution of the loop.

There are certainly other problems too, but I haven't looked further.

Read about comma operator

edited Dec 13 '18 at 08:18

Gelldur

11,187
7
57
68

answered Dec 13 '18 at 08:15

Peter

35,646
4
32
74

WOW ........thanks for this . This thing was no where explained . replacing i<=n,completed==0 with i<=n && completed==0 works , but still , they are just used for checking , so why the value obtained by the function is diffrent from the value provided to it ? – harshraj22 Dec 13 '18 at 08:22
2

The error causes the loops to run over ranges that are not expected. Since `dfs()` is recursive, you're probably getting confused about which value is passed to which recursive call. – Peter Dec 13 '18 at 08:37
at least the first one should be correct . the first print should be 1 1 . isn't it ? – harshraj22 Dec 13 '18 at 08:51
1

Depends. Without knowing what inputs you're providing to your program - since you haven't provided an example of your input - it's impossible to say, There are plenty of ways - depending on values input to it - that your program can have undefined behaviour - particularly since your array indexing is off by 1 (C++ array indexing is zero based). When behaviour is undefined, results can be quite counter-intuitive - and there is no point in explaining why it manifests in any particular way. – Peter Dec 13 '18 at 09:02
I think you may try the problem link provided . It contains some test cases . – harshraj22 Dec 13 '18 at 09:06

Function receiving different value than passed

1 Answers1