Advertisement
a_chn

Untitled

Feb 3rd, 2024
937
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int,int> pii;
  5. # define im INT_MAX
  6. # define umap unordered_map
  7. # define uset unordered_set
  8. # define f first
  9. # define s second
  10. # define pq priority_queue
  11. # define pb push_back
  12. # define ins insert
  13. # define INF LLONG_MAX
  14. #define int long long
  15. int n, m;
  16. map<pii,vector<pii>> switches;
  17. int on[102][102]; bool visited[102][102];
  18.  
  19.  
  20. void floodfill(){
  21.     // cout << "i: " << i << ", j: " << j << '\n';
  22.     queue<pii> q; q.push({1,1});
  23.  
  24.     while (q.size()){
  25.         // cout << "queue: "; printQueuePair(q); cout << '\n';
  26.         int i=q.front().f; int j=q.front().s; q.pop();
  27.         // cout << "i: " << i << ", j: " << j << '\n';
  28.         for (pii room : switches[{i,j}]){ // switch on everything from the current room
  29.             if (!on[room.f][room.s]){
  30.                 on[room.f][room.s] = true;
  31.                 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]){
  32.                     visited[room.f][room.s] = true;
  33.                     q.push(room);
  34.                 }
  35.             }
  36.         }
  37.         if (on[i+1][j] && !visited[i+1][j]){ // if (i+1,j) is in range, on, and unvisited
  38.             visited[i+1][j] = true; // mark as visited
  39.             q.push({i+1,j}); // queue it
  40.         }
  41.         if (on[i-1][j] && !visited[i-1][j]){
  42.             visited[i-1][j] = true;
  43.             q.push({i-1,j});
  44.         }
  45.         if (on[i][j+1] && !visited[i][j+1]){
  46.             visited[i][j+1] = true;
  47.             q.push({i,j+1});
  48.         }
  49.         if (on[i][j-1] && !visited[i][j-1]){
  50.             visited[i][j-1] = true;
  51.             q.push({i,j-1});
  52.         }
  53.     }
  54.  
  55.  
  56. }
  57.  
  58. main(){
  59.     ifstream cin("lightson.in");  
  60.     ofstream cout("lightson.out");
  61.  
  62.     cin >> n >> m;
  63.     for (int i=0; i<m; i++){
  64.         int x, y, a, b; cin >> x >> y >> a >> b;
  65.         switches[{x,y}].pb({a,b});
  66.     }
  67.  
  68.     // printPairContPairMap(switches);
  69.     on[1][1] = true;
  70.     visited[1][1] = true;
  71.     floodfill();
  72.  
  73.     // cout << "on:\n"; print2dArray(on,n+1,n+1);
  74.     // cout << "visited:\n"; print2dArray(visited,n+1,n+1);
  75.  
  76.     int lit_rooms = 0;
  77.     for (int i=1; i<=n; i++){
  78.         for (int j=1; j<=n; j++){
  79.             lit_rooms += on[i][j];
  80.         }
  81.     }
  82.  
  83.     cout << lit_rooms << '\n';
  84.  
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement