USACO 2016 January Contest, Silver Problem 3. Build Gates. Why is my answer not giving an output?

Problems and Contests
#1

Here is my code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;

#define ar array
#define ll long long
const int MAXN = 1e5 + 1;
bool visited [5000][5000];
int game[5000][5000];
void floodfill(int r, int c, int color){
    if(r < 0 || r > 5000 || c < 0 || c > 5000) return; 
    if(game[r][c] != 0) return; 
    if(visited[r][c]) return; 
    visited[r][c] = true;
    floodfill(r, c+1, color);
    floodfill(r, c-1, color);
    floodfill(r-1, c, color);
    floodfill(r+1, c, color);
}
int main() {
    /* freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); */
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
ll n, x, y;
x=2500;
y=2500;
cin >> n;
char a;
for (int i = 0; i < n; i++)
{
    cin >> a;
    if(a=='N') {
        game[x][y+1]=1;
        game[x][y+2]=1;
        y+=2;
    }
    if(a=='S') {
        game[x][y-1]=1;
        game[x][y-2]=1;
        y-=2;
    }
    if(a=='E') {
        game[x+1][y]=1;
        game[x+2][y]=1;
        x+=2;
    }
    if(a=='W') {
        game[x-1][y]=1;
        game[x-2][y]=1;
        x-=2;
    }
}
int ans(0);
for (int i = 0; i < 5000; i++)
{
    for (int j = 0; j < 5000; j++)
    {
        if(game[i][j]==0&&visited[i][j]==0) { 
            ans++;
            floodfill(i,j,0);
        }
    }
    
}
cout << ans;

}

I am basically just making a 2d array, laying the fences, and using floodfill to find all the regions. I don’t understand why I am getting no output.

#2

Could you first format your code?
Also, it should be pretty easy to just debug the code yourself. Why don’t you step through your code with a debugger and see what goes wrong?

#3

There is no error it seems (no errors when compiling a running). I think there is a bounding issue, but I am unsure.

#4

Recently someone else posted a similar issue for this problem: Floodfill 2016 January Silver Problem 3. You must either use a stack or a queue to do the DFS/BFS, because recursion of depth 5000*5000 = 25e6 will crash.

Also your arrays are 5000 in size which means that you can only index on [0, 4999] inclusive, but you are checking if(r < 0 || r > 5000 || c < 0 || c > 5000).

#5

Alternatively, you can bound your search further.

Since you double FJ’s segment lengths, the array coordinates have to be in the range [−2N−1,2N+1], which you can transpose to [0,4N+3). Your 2D array should have dimensions 4003\times 4003.

To condense it further, you can calculate a bounding box with minX , maxX , minY , maxY. Make sure to increment maxX and maxY by 1 and decrement minX and minY by 1, so you get all appropriate regions. Since the sum of FJ’s step lengths is at most 2000, the maximum area you will floodfill on is 10002 \times10002 by AM-GM.

#6

Wouldn’t a recursion of depth 10002 x 10002 crash?

#7

It’s actually 1002 \times 1002, I think that was just a typo.

#8 
#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <set>

#include <functional>

#include <numeric>

#include <utility>

#include <limits>

#include <time.h>

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

using namespace std;

#define ll long long

const int MAXN = 1e5 + 1;

bool visited [4001][4001];

int game[4001][4001];

ll xmin=100000, xmax=-100000,ymin=100000,ymax=-100000;

void floodfill(int r, int c){

    if(r < xmin-1 || r > xmax+1 || c < ymin-1 || c > ymax+1) return; 

    if(game[r][c] != 0) return; 

    if(visited[r][c]) return; 

    visited[r][c] = true;

    floodfill(r, c+1);

    floodfill(r, c-1);

    floodfill(r-1, c);

    floodfill(r+1, c);

}

int main() {

     freopen("gates.in", "r", stdin);

    freopen("gates.out", "w", stdout); 

    ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

ll n, x, y;

x=2000;

y=2000;

cin >> n;

char a;

for (int i = 0; i < n; i++)

{

    cin >> a;

    if(a=='N') {

        game[x][y+1]=1;

        game[x][y+2]=1;

        y+=2;

    }

    if(a=='S') {

        game[x][y-1]=1;

        game[x][y-2]=1;

        y-=2;

    }

    if(a=='E') {

        game[x+1][y]=1;

        game[x+2][y]=1;

        x+=2;

    }

    if(a=='W') {

        game[x-1][y]=1;

        game[x-2][y]=1;

        x-=2;

    }

    xmin=min(x,xmin);

    xmax=max(x,xmax);

    ymax=max(y,ymax);

    ymin=min(y,ymin);

}

int ans=0;

for (int i = xmin-1; i <= xmax+1; i++)

{

    for (int j = ymin-1; j <= ymax+1; j++)

    {

         if(visited[i][j]==0) { 

            if(game[i][j]==0) { 

                floodfill(i,j);

                ans++;

            }

        } 

    }

    

}

cout << ans-1;

}

This worked perfectly. This is the AC code for those who see this later. Thanks for all the help.

#9

Good job! I had a similar idea in this thread. @infimum gave a great idea in post #3, so you can reference my thread for how I got AC using a stack-based DFS. The stack theoretically runs in time because the machine isn’t designed to recurse 16\cdot 10^6 deep, but it could allocate that much memory on a stack. I personally would bound the search and make adjustments like incrementing the maxs and decrementing mins, but note that using a stack for DFS or a queue for BFS is also an option.