USACO 2015 December Contest Silver Division - Switching on the Lights

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem is a typical graph problem where we have to traverse the graph created by the lights we can turn on starting from \((1, 1)\). As we progress with the BFS traversal, we can keep turning on lights and as long as we can visit cells which are lighted, we will move on.

The final answer consists of the number of cells we managed to light during the algorithm.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<pair<int, int> > v[102][102];

bool viz[102][102];
bool col[102][102];

int ox[] = {-1, 0, 1, 0};
int oy[] = {0, 1, 0, -1};
int main() {

    ifstream cin("lightson.in");
    ofstream cout("lightson.out");

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v[a][b].push_back({c, d});
    }
    viz[1][1] = col[1][1] = 1;
    queue<pair<int, int> > q;
    q.push({1, 1});
    while (!q.empty()) {
        pair<int, int> node = q.front();
        q.pop();
        for (auto x : v[node.first][node.second]) {
            col[x.first][x.second] = 1;
            if (!viz[x.first][x.second])
                for (int i = 0; i <= 3; ++i) {
                    int nxtX = x.first + ox[i];
                    int nxtY = x.second + oy[i];
                    if (nxtX >= 1 && nxtX <= n && nxtY >= 1 && nxtY <= n && viz[nxtX][nxtY]) {
                        viz[x.first][x.second] = 1;
                        q.push({x.first, x.second});
                        break;
                    }
                }
        }
        for (int i = 0; i <= 3; ++i) {
            int nxtX = node.first + ox[i];
            int nxtY = node.second + oy[i];
            if (nxtX >= 1 && nxtX <= n && nxtY >= 1 && nxtY <= n && !viz[nxtX][nxtY] && col[nxtX][nxtY]) {
                viz[nxtX][nxtY] = 1;
                q.push({nxtX, nxtY});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            ans += col[i][j];
        }
    }
    cout << ans;
    return 0;
}