YEZAELP

CUBE-027: หลอดไฟ (Bulb)

Dec 23rd, 2020 (edited)
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 2e9;
  6.  
  7. using pii = pair <int, int>;
  8.  
  9. int main(){
  10.  
  11.     int a;
  12.     scanf("%d", &a);
  13.  
  14.     int n = 0;
  15.     for(int i = a-1; i >= 0; i--){
  16.         int x;
  17.         scanf("%d", &x);
  18.         n += x << i;
  19.     }
  20.  
  21.     vector <int> dis(1<<21, INF);
  22.     vector <bool> visited(1<<21, false);
  23.     priority_queue <pii, vector <pii>, greater <pii>> pq;
  24.  
  25.     dis[n] = 0;
  26.     pq.push({0, n});
  27.  
  28.     while(pq.size() > 0){
  29.         int Bit, d;
  30.         d = pq.top().first;
  31.         Bit = pq.top().second;
  32.         pq.pop();
  33.  
  34.         if(visited[Bit])
  35.             continue;
  36.         visited[Bit] = true;
  37.  
  38.         if(Bit == 0) {
  39.             printf("%d", d);
  40.             return 0;
  41.         }
  42.  
  43.         for(int i = 0; i < a; i++){
  44.             int bit = Bit ^ (1 << i);
  45.             if(i != 0) bit = bit ^ (1 << (i-1));
  46.             if(i != a-1) bit = bit ^ (1 << (i+1));
  47.             if(!visited[bit] and d + 1 < dis[bit]){
  48.                 dis[bit] = d + 1;
  49.                 pq.push({dis[bit], bit});
  50.             }
  51.         }
  52.     }
  53.  
  54.     printf("-1");
  55.  
  56.     return 0;
  57. }
  58. /*
  59. 5
  60. 1 1 0 1 1
  61. */
  62.  
RAW Paste Data Copied