# Switching on the Lights

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;
}


Did you try this this already? \quad

What’s stopping your code from lighting up a room that doesn’t have the lights on?
Doesn’t this just light up every single room?

I think this would allow Bessie to turn on switches that shouldn’t be turned on since the room they are in is dark.

It doesn’t light up every single room because the !lights[i][j] checks to see that the room doesn’t have it’s light on, and only then turns the light on and implements floodfill.

Try debugging this test case:
2 3
1 1 2 2
2 2 1 2
2 2 2 1

If I understand the question correctly, the answer should be 2 (only (1,1) and (2,2) are lit), but your program outputs 3. The issues I see with your code is that the nested for loop I mentioned goes over rooms that haven’t been lit up yet (why are you floodfilling a room if the light isn’t on?), and you can also access rooms that are not reachable (eg: floodfilling (2,2) even though Bessie can’t reach it from (1,1))