Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> pii;
- # define im INT_MAX
- # define umap unordered_map
- # define uset unordered_set
- # define f first
- # define s second
- # define pq priority_queue
- # define pb push_back
- # define ins insert
- # define INF LLONG_MAX
- #define int long long
- int n, m;
- map<pii,vector<pii>> switches;
- int on[102][102]; bool visited[102][102];
- void floodfill(){
- // cout << "i: " << i << ", j: " << j << '\n';
- queue<pii> q; q.push({1,1});
- while (q.size()){
- // cout << "queue: "; printQueuePair(q); cout << '\n';
- int i=q.front().f; int j=q.front().s; q.pop();
- // cout << "i: " << i << ", j: " << j << '\n';
- for (pii room : switches[{i,j}]){ // switch on everything from the current room
- if (!on[room.f][room.s]){
- on[room.f][room.s] = true;
- if (visited[room.f+1][room.s] || visited[room.f-1][room.s] || visited[room.f][room.s+1] || visited[room.f][room.s-1]){
- visited[room.f][room.s] = true;
- q.push(room);
- }
- }
- }
- if (on[i+1][j] && !visited[i+1][j]){ // if (i+1,j) is in range, on, and unvisited
- visited[i+1][j] = true; // mark as visited
- q.push({i+1,j}); // queue it
- }
- if (on[i-1][j] && !visited[i-1][j]){
- visited[i-1][j] = true;
- q.push({i-1,j});
- }
- if (on[i][j+1] && !visited[i][j+1]){
- visited[i][j+1] = true;
- q.push({i,j+1});
- }
- if (on[i][j-1] && !visited[i][j-1]){
- visited[i][j-1] = true;
- q.push({i,j-1});
- }
- }
- }
- main(){
- ifstream cin("lightson.in");
- ofstream cout("lightson.out");
- cin >> n >> m;
- for (int i=0; i<m; i++){
- int x, y, a, b; cin >> x >> y >> a >> b;
- switches[{x,y}].pb({a,b});
- }
- // printPairContPairMap(switches);
- on[1][1] = true;
- visited[1][1] = true;
- floodfill();
- // cout << "on:\n"; print2dArray(on,n+1,n+1);
- // cout << "visited:\n"; print2dArray(visited,n+1,n+1);
- int lit_rooms = 0;
- for (int i=1; i<=n; i++){
- for (int j=1; j<=n; j++){
- lit_rooms += on[i][j];
- }
- }
- cout << lit_rooms << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement