Switching On The Lights: USACO 2015, Silver. Problem 1.
Link: https://usaco.org/index.php?page=viewproblem2&cpid=570
My time (not the hit bo-en song): 46:34:69
Sidenote: Take everything I say with a LARGE grain of salt; my posts are meant to be an exercise to cement my ideas after coding a problem. I may very well be wrong.
Problem summary:
There is an N by N grid (2<=N<=100) representing rooms in a barn, numbered (1,1) to (N,N). Bessie starts at room (1,1), there are light switches that she can use to turn on the lights of other rooms. Bessie can only move through lit up rooms, find the max number of lit rooms Bessie can make.
Explanation:
Note: One cannot naively use DFS when solving this question, rooms continuously update and DFS does not allow one to check through all rooms. This leaves one with an answer which is under-counted, and unfortunately wrong.
Tricks I employed: - Resize all vectors to have walls, to prevent needing to check whether I go out of bounds - *Checking vis to see if a room is connected to the larger connected component - dx and dy to quickly check neighbors
This problem is like any other generic flood fill problem, the only thing that sets it apart is how the graph changes as she turns on the lights. As Bessie turns on more and more lights, there are new routes to explore that she could not go through initially. So, I used a BFS approach which allows floodfill to "go back" and check. To implement this, every time I encountered a room I checked if it was a neighbor to the main component, if it is I add it to the queue of rooms to check and add it to the main component itself. This way, I don't undercount.
Code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define str string
#define vec vector
#define prq priority_queue
#define mprq(x) priority_queue<x, vec<x>, greater<x>>
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define print(x) for(auto i : x) {cout << i << " ";} cout << endl;
#define cinVec(x) for(auto& i : x) cin >> i;
int n, m;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vec<vec<bool>> lit;
vec<vec<bool>> vis;
vec<vec<vec<pair<int, int>>>> switches; //this is ... a monster.
int ans = 1;
void fast_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
}
void flood(pair<int, int> pos){
// BFS + flood
queue<pair<int, int>> next; next.push(pos);
vis[pos.first][pos.second] = true;
while(!next.empty()){
auto [x, y] = next.front(); next.pop();
for(auto& i : switches[x][y]){
auto [x_, y_] = i;
if(!lit[x_][y_]){
++ans;
lit[x_][y_] = true;
FOR(j, 0, 4){
if(vis[x_+dx[j]][y_+dy[j]]){
next.push({x_, y_});
vis[x_][y_] = true;
break;
}
}
}
}
FOR(i, 0, 4){
auto x_ = x+dx[i], y_ = y+dy[i];
if(lit[x_][y_] && !vis[x_][y_]){
vis[x_][y_] = true;
next.push({x_, y_});
}
}
}
}
int main(){
//freopen("lightson.in", "r", stdin); freopen("lightson.out", "w", stdout);
fast_io();
//taking input
cin >> n >> m;
lit.resize(n+2, vec<bool>(n+2, false));
vis.resize(n+2, vec<bool>(n+2, false));
switches.resize(n+2, vec<vec<pair<int,int>>>(n+2));
lit[1][1] = true;
int a, b, x, y;
FOR(i, 0, m){
cin >> a >> b >> x >> y;
switches[a][b].push_back({x, y});
}
//solving
flood({1, 1});
cout << ans << endl;
return 0;
}
Afterthought:
Hello! I'm back with more ramblings, this time I know that there are actual people reading this so,,, yeah! I did use a hint on this problem because I wasn't entirely sure how to check through all the rooms; now I know I can use vis to track which items may be associated with the main component. Also know that as time goes on -- if I continue to post -- I will put significantly less effort into these (^-^).
PS. I'm not that great with programming, so if there is anything I can improve upon PLEASE let me know (that is, critique me all you want). PS.PS. HAPPY NEW YEAR (a few more hours for me)! Let's all improve this year, I for one hope to drag up my elo and not fail in USACO. - Quasistarsupernova.
