Why does my program give runtime error after removing the comments in the code below?

Question

There is a field with plants — a grid with N rows (numbered 1 through N) and M columns (numbered 1 through M); out of its NM cells, K cells contain plants, while the rest contain weeds. Outside this grid, there are weeds everywhere. Two cells are adjacent if they have a common side.

You want to build fences in the field in such a way that the following conditions hold for each cell that contains a plant:

it is possible to move from this cell to each adjacent cell containing a plant without crossing any fences it is impossible to move from this cell to any cell containing weeds without crossing any fences

Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains three space-separated integers N, M and K. K lines follow. Each of these lines contains two space-separated integers r and c denoting that the cell in row r and column c contains a plant.

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

int main() {
    // your code goes here
    int t,n,m,i,j,k,flag=0;
    int r[4] = {-1,1,0,0};
    int c[4] = {0,0,-1,1};
    cin>>t;
    while(t--) {
        int ans=0;
        cin>>n>>m>>k;
      vector < vector<int> >  vec(n, vector<int>(m,0));

      /* for(int z=0; z<k; z++) {
            cin>>i>>j;
            vec[i-1][j-1] = 1;
        } */
        queue<pair<int,int>> q;
        for(i=0;i<n;i++) {
            for(j=0;j<m;j++) {
                if(vec[i][j] == 1) {
                    q.push(make_pair(i,j));
                    flag = 1;
                    break;
                }
            }
            if(flag==1)
            break;
        }
        while(!q.empty()) {
            pair<int,int> p = q.front();
            int a = p.first;
            int b = p.second;
          int x=0;
            q.pop();
            for(i=0;i<4;i++) {
                for(j=0;j<4;j++) {
                    int rr = a + r[i];
                    int cc = b + c[j];
                    if(rr<0 || cc<0 || rr>=n || cc>=m || vec[rr][cc]==0)
                    continue;
                    else {
                        q.push(make_pair(rr,cc));
                        x++;
                    }
                }
            }
            ans = ans + (4-x);
        }
         cout<<ans<<endl;

    }
    return 0;
}

If I remove the comments above, it shows timeout error. I'm unable to detect the problem with the above statement.

you appear to be using i and j for inputs r and c, and defining r and c at the start. why? — Tzalumen, Apr 09 '19 at 15:22
Short answer is what the other individual said: your algorithm is running too long. It runs over when you remove the commented lines because those are the lines populating your vector matrix, and your algorithm does no work over an unpopulated matrix (as one would expect). — Tzalumen, Apr 09 '19 at 15:26
The commented section waits for the user to provide an input. So the interface of your program is completely different. If you don't adjust the input accordingly, it's normal for the behavior to be different. If the input *is* different, it's not clear what that input is. — François Andrieux, Apr 09 '19 at 15:26
@FrançoisAndrieux I recognize the style of this, the commented out section takes piped-in test input. This looks like a problem off HackerRank or a similar site. — Tzalumen, Apr 09 '19 at 15:27
Also, Nikita, the timeout is not a runtime error, it is a failure state from whatever challenge site you are on, indicating your solution solves the problem too slowly. Your code may compile and run and be perfectly stable legal code that solves the problem correctly, it's just too slow for your challenge. Which I am going to guess is because based on your loop nesting that appears to be O(n^3) or O(n^4). — Tzalumen, Apr 09 '19 at 15:31
@Nikita, the behavior strongly depends on input. Please provide the (simplified) input which produces the timeout. — nVxx, Apr 09 '19 at 16:14
Good practice: Always check user input for validity (check stream state as well!). You get around quite a lot of trouble if user enters something invalid... — Aconcagua, Apr 09 '19 at 16:22
About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... — Aconcagua, Apr 09 '19 at 16:22
The flag needed for exiting from the nested loop is pretty ugly. Would be one of the (rather few) cases where use of `goto` would be valid. A lambda `return`ing from nested loop is an alternative... — Aconcagua, Apr 09 '19 at 16:53
You don't need the double loop at all, if you remember first pair to start with right while reading all the pairs from user input. — Aconcagua, Apr 09 '19 at 16:59

Aconcagua · Accepted Answer · 2019-04-09T16:45:46.017

Let's assume user set a 1 for both of the pairs (6, 7) and (7, 7).

Then the following will happen:

first pair to be discovered will be (6, 7)
for pair (6, 7), pair (7, 7) will be added to the queue
for pair (7, 7), pair (6, 7) will be added again (but was removed previously)
for pair (6, 7), pair (7, 7) will be added again
...

So your loop won't terminate ever if there's just one single pair of neighbouring pairs (and the problem will be worse with larger groups).

If you want to avoid that, you could set vec[rr][cc] = 0 once you've visited the field; alternatively, you could set vec[rr][cc] = -1 (or any other value different from 0 and 1), then you could distinguish: 1, unvisited 0 (yet with same value), visited 0 (changed to -1). You'd need to adjust your check, though:

if(0 <= rr && rr < n && 0 <= cc && cc < m && vec[rr][cc] == 1)
// ...

because skipping on == 0 won't work any more (re-ordering the comparisons is not necessary, but the way it is now it ressembles closer mathematical equation 0 <= rr <= n, which, of course, cannot be written this way in C++).

Why does my program give runtime error after removing the comments in the code below?

1 Answers1