/* http://usaco.org/index.php?page=viewproblem2&cpid=570 (create a free account) USACO 2015 December Silver Ques. 1: Switching on the Lights This code is not for Sololearn, I recommend onlinegdb.com or visual studio code Make a file named paint.in and put in: 3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1 Output: 5 I recommend not copying this code into USACO though it works cause you need to do it yourself. */ #include #include // #include #include using namespace std; typedef pair pii; vector> grid; vector> visited; vector>> sw; int n, m; void rec(int x, int y) { int xs[4] = {-1, 1, 0, 0}; int ys[4] = {0, 0, -1, 1}; bool isvalid = false; if(!(x == 0 && y == 0)){ int nx = 0, ny = 0; int check = 0; for (int i = 0; i < 4; i++) { nx = xs[i] + x; ny = ys[i] + y; if (0 <= nx && nx < n && 0 <= ny && ny < n && grid[nx][ny]==1 && visited[nx][ny]==1){ isvalid=true; } } } if (isvalid || (x==0 && y==0) ) { visited[x][y] = 1; // cout << x << " " << y << endl; // if (x==3 && y==3) { // cout << "Hi" << endl; // } for (int i = 0; i < sw[x][y].size(); i++) { grid[sw[x][y][i].first][sw[x][y][i].second] = 1; } // neighboring room to go to for (int i = 0; i < 4; i++) { int nx, ny; nx = xs[i] + x; ny = ys[i] + y; if ((0 <= nx && nx < n) && (0 <= ny && ny < n) && grid[nx][ny] == 1 && visited[nx][ny] == 0) { rec(nx, ny); } } // lit rooms for (int i = 0; i < sw[x][y].size(); i++) { if (!visited[sw[x][y][i].first][sw[x][y][i].second]) { rec(sw[x][y][i].first, sw[x][y][i].second); } } } } int main() { ifstream fin("lightson.in"); ofstream fout("lightson.out"); fin >> n >> m; grid.reserve(n); grid.resize(n, vector(n)); visited.reserve(n); visited.resize(n, vector(n)); grid[0][0] = 1; sw.resize(n); for (int i = 0; i < m; i++) { int x, y, a, b; fin >> x >> y >> a >> b; sw[x - 1][y - 1].push_back({a - 1, b - 1}); } rec(0, 0); int result = 0; for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { result += grid[x][y]; } } fout << result << endl; fout.close(); fin.close(); return 0; }

USACO #26 Switching on the LIghts C++