MATU's Solution to the 2015 December USACO Silver Division Barn Problem

lightson.java

/*
ID: -snip-
LANG: JAVA
TASK: lightson
 */
import java.io.*;
import java.util.*;

class lightson {
	static class Switch {
		int x, y, turnsOnX, turnsOnY;

		public Switch(int x, int y, int turnsOnX, int turnsOnY) {
			this.turnsOnX = turnsOnX - 1;
			this.turnsOnY = turnsOnY - 1;
			this.x = x - 1;
			this.y = y - 1;
			println("Switch created at " + x + " " + y + " to " + turnsOnX
					+ " " + turnsOnY);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new FileReader("lightson.in"));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
				"lightson.out")));

		StringTokenizer tok = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(tok.nextToken());
		// why are N and M always reversed?
		int M = Integer.parseInt(tok.nextToken());

		@SuppressWarnings("unchecked")
		List<Switch>[][] switches = new ArrayList[N][N];
		boolean[][] rooms = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				rooms[i][j] = false;
			}
		}
		rooms[0][0] = true;

		for (int i = 0; i < M; i++) {
			tok = new StringTokenizer(in.readLine());
			int x = Integer.parseInt(tok.nextToken());
			int y = Integer.parseInt(tok.nextToken());
			Switch switch_ = new Switch(x, y,
					Integer.parseInt(tok.nextToken()), Integer.parseInt(tok
							.nextToken()));
			if (switches[x - 1][y - 1] == null) {
				switches[x - 1][y - 1] = new ArrayList<Switch>();
			}
			switches[x - 1][y - 1].add(switch_);
		}

		boolean[][] completedRooms = new boolean[N][N];

		// keep going around and turning on switches until no more switches are
		// left

		int loopsAfterNoLights = 0;
		do {
			turnedOnLightsInFill = false;
			numRoomsFilled = 0;
			// clear completedRooms array
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					completedRooms[i][j] = false;
				}
			}
			// flood fill to find new switches
			floodFill(0, 0, switches, rooms, N, completedRooms);
			println("Step completed, currently " + numRoomsFilled + " lit");
			if (!turnedOnLightsInFill)
				loopsAfterNoLights++;
			else
				loopsAfterNoLights = 0;
		} while (turnedOnLightsInFill && loopsAfterNoLights < 5);

		// calculate how many lights on
		numRoomsFilled = 0;
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				if (rooms[x][y])
					numRoomsFilled++;
			}
		}
		out.println(numRoomsFilled);
		System.out.println(numRoomsFilled);

		out.close();
		in.close();
	}

	static boolean turnedOnLightsInFill = false;
	static int numRoomsFilled = 0;

	public static void floodFill(int x, int y, List<Switch>[][] switches,
			boolean[][] rooms, int N, boolean[][] completedRooms) {
		// if unlit, we can't go here
		if (!rooms[x][y])
			return;

		// we already went here
		if (completedRooms[x][y]) {
			return;
		}

		completedRooms[x][y] = true;

		List<Switch> switchList = switches[x][y];
		if (switchList != null) {
			for (int i = 0; i < switchList.size(); i++) {
				Switch switch_ = switchList.get(i);
				if (!rooms[switch_.turnsOnX][switch_.turnsOnY]) {
					println("Turned on room " + switch_.turnsOnX + " "
							+ switch_.turnsOnY);
					rooms[switch_.turnsOnX][switch_.turnsOnY] = true;
					turnedOnLightsInFill = true;
				}
			}
		}

		numRoomsFilled++;
		if (x + 1 < N) {
			floodFill(x + 1, y, switches, rooms, N, completedRooms);
		}
		if (x - 1 > -1) {
			floodFill(x - 1, y, switches, rooms, N, completedRooms);
		}
		if (y + 1 < N) {
			floodFill(x, y + 1, switches, rooms, N, completedRooms);
		}
		if (y - 1 > -1) {
			floodFill(x, y - 1, switches, rooms, N, completedRooms);
		}
	}

	static void println(String s) {
	  // disabled in submission for max performance
		// System.out.println(s);
	}
}