In the USACO problem Switching on the Lights(link: https://usaco.guide/silver/ff#problem-http://www.usaco.org/index.php?page=viewproblem2&cpid=570) my code below only runs for the first 2 testcases.
My approach is to basically iterate through every point, check that it hasn’t been visited and the lights are off in that room. If those 2 conditions are met, I floodfill that specific point.
In my floodfill, I check that the room has not been visited before and that the lights are on in that room. Then I iterate through every corresponding switch for that particular room and turn the lights of those rooms on. After that I floodfill in all directions.
Can someone please tell me where I went wrong?
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lightson.in");
ofstream fout("lightson.out");
bool lights[101][101];
bool visited[101][101];
int n,m;
map<pair<int,int>,vector<pair<int,int>>> lightPos;
int currSize = 0;
const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
void ff(int x, int y){
if(x<0||x>=n||y<0||y>=n||!lights[x][y]||visited[x][y]) return;
visited[x][y] = true;
currSize++;
for(auto elem: lightPos[{x,y}]){
lights[elem.first][elem.second] = true;
}
for(int i=0; i<4; i++) ff(x+xd[i], y+yd[i]);
}
int main() {
fin>>n>>m;
for(int i=0; i<m; i++){
int x,y,a,b;
fin>>x>>y>>a>>b;
x--,y--,a--,b--;
lightPos[{x,y}].push_back({a,b});
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
lights[i][j] = false;
visited[i][j] = false;
}
}
int maxSize = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
currSize = 0;
if(!lights[i][j]&&!visited[i][j]){
lights[i][j] = true;
ff(i,j);
maxSize = max(currSize, maxSize);
}
}
}
fout<<maxSize;
}