Link to the problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=596.
I understand the idea of doubling FJ’s path segments so that each enclosed region contains at least one point inside it. Then we can use floodfill to find the number of connected regions in the graph, being careful to exclude the points that FJ has visited in the floodfill.
Please note that the coordinates in the problem vary between [-2N, 2N]. I want my array coordinates in the range [-2N-1, 2N+1], so we can traverse through the outer boundaries of the (potentially infinite) grid. Incrementing each coordinate by 2N+1 transposes the range of array indices to [0, 4N+3).
#include <bits/stdc++.h>
using namespace std;
const int MX = 4003;
int N;
string s;
bool vis[MX][MX], FJ[MX][MX];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void ff(int x, int y){
vis[x][y] = true;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= 4*N+3 || ny < 0 || ny >= 4*N+3){
continue;
}
if(FJ[x][y] || vis[nx][ny]){
continue;
}
ff(nx, ny);
}
}
int main(){
freopen("gates.in","r",stdin);
freopen("gates.out","w",stdout);
cin >> N >> s;
// double the lengths of segments so
// there's at least 1 point inside each enclosed region
int cx = 2*N+1, cy = 2*N+1; // FJ starts at the origin
FJ[cx][cy] = true;
for(char c : s) for(int i=0; i<2; i++){
switch(c){
case 'N':
cy++;
break;
case 'E':
cx++;
break;
case 'W':
cx--;
break;
case 'S':
cy--;
break;
}
FJ[cx][cy] = true;
}
int R = 0;
// find the number of connected regions
for(int i=0; i<MX; i++){
for(int j=0; j<MX; j++){
if(!FJ[i][j] && !vis[i][j]){
R++;
ff(i, j);
}
}
}
cout << R-1 << endl;
}
I checked that this code is very similar to the internal solution provided on the USACO Guide. However, my code gives a memory limit or runtime error when I run it.
The submission succeeds with 7/10 test cases if I instead make the following bound replacements.
- Change the out-of-bounds base case in the floodfill function to
if(nx < 0 || nx >= 2*N || ny < 0 || ny >= 2*N){ // supposed to be nx >= MX || ny >= MX
continue;
}
- Change the origin point of cx and cy to
int cx = N, cy = N; // origin is supposedly (2N+1, 2N+1)
- Modify the iterative loops when finding the connected regions to
for(int i=0; i<2*N; i++){ // supposed to be i<MX
for(int j=0; j<2*N; j++){ // supposed to be j<MX
if(!FJ[i][j] && !vis[i][j]){
R++;
ff(i, j);
}
}
}
Can you please explain why I receive a “runtime error or memory limit exceed” exception in my original code? The memory limit is greater than 4003^2, and I don’t think I access an out-of-bounds array index anywhere.
