ccbeginner

UVa Q321

Jan 20th, 2020
136
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q321
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int r,d,s;
  6. bool pass[11][11];
  7. bool ctrl[11][11];//ctrl[a][b] := a control b room light
  8. bool vis[1<<11][11];
  9.  
  10. struct status{
  11.     int cur, loc;
  12. };
  13. status pre[1<<11][11];//for back trace usage
  14.  
  15. int32_t main(){
  16.     int cnt = 0;
  17.     while(cin >> r >> d >> s){
  18.         if(r == 0 && d == 0 && s == 0)break;
  19.         memset(pass, 0, sizeof(pass));
  20.         memset(ctrl, 0, sizeof(ctrl));
  21.         memset(vis, 0, sizeof(vis));
  22.         for(int i = 0; i < d; ++i){
  23.             int a,b;
  24.             cin >> a >> b;
  25.             pass[a][b] = pass[b][a] = 1;
  26.         }
  27.         for(int i = 0; i < s; ++i){
  28.             int a,b;
  29.             cin >> a >> b;
  30.             if(a != b)ctrl[a][b] = 1;//a control b
  31.         }
  32.         //bfs
  33.         deque<status> dq;
  34.         status T={.cur = (1<<1), .loc = 1};
  35.         vis[T.cur][T.loc] = 1;
  36.         dq.emplace_back(T);
  37.         bool fnd = 0;
  38.         while(!dq.empty() && !fnd){
  39.             T = dq.front();
  40.             dq.pop_front();
  41.             if(T.cur == (1<<r)){
  42.                 fnd = 1;
  43.                 break;
  44.             }
  45.             //////////////////////////////////
  46.             //printf("%o %d\n", T.cur, T.loc);
  47.             for(int i = 1; i <= r; ++i){
  48.                 if(!vis[T.cur][i] && pass[T.loc][i] && (T.cur & (1 << i))){//move
  49.                     status tmd={.cur = T.cur, .loc = i};
  50.                     pre[tmd.cur][tmd.loc] = T;
  51.                     vis[tmd.cur][tmd.loc] = 1;
  52.                     dq.emplace_back(tmd);
  53.                     if(tmd.cur == (1<<r)){
  54.                         fnd = 1;
  55.                         break;
  56.                     }
  57.                 }
  58.                 int nxt = T.cur ^ (1 << i);
  59.                 if(!vis[nxt][T.loc] && ctrl[T.loc][i] && !vis[nxt][T.loc]){//switch
  60.                     status tmd{.cur = nxt, .loc = T.loc};
  61.                     pre[tmd.cur][tmd.loc] = T;
  62.                     vis[tmd.cur][tmd.loc] = 1;
  63.                     dq.emplace_back(tmd);
  64.                     if(tmd.cur == (1<<r)){
  65.                         fnd = 1;
  66.                         break;
  67.                     }
  68.                 }
  69.             }
  70.             //////////////////////////////////
  71.         }
  72.         cout << "Villa #" << ++cnt << '\n';
  73.         if(fnd){
  74.             vector<status> v;
  75.             status U{.cur = (1<<r), .loc = r};
  76.             while(U.cur != 1<<1){
  77.                 v.emplace_back(U);
  78.                 U = pre[U.cur][U.loc];
  79.             }
  80.             cout << "The problem can be solved in " << v.size() << " steps:\n";
  81.             while(!v.empty()){
  82.                 T = v.back();//U => T
  83.                 if(U.loc != T.loc){
  84.                     cout << "- Move to room " << T.loc << ".\n";
  85.                 }else{
  86.                     int k = 0;
  87.                     while((T.cur & (1 << k)) == (U.cur & (1 << k)))++k;
  88.                     if(U.cur & (1 << k))cout << "- Switch off light in room " << k << ".\n";
  89.                     else cout << "- Switch on light in room " << k << ".\n";
  90.                 }
  91.                 U = T;
  92.                 v.pop_back();
  93.             }
  94.         }else{
  95.             cout << "The problem cannot be solved.\n";
  96.         }
  97.         cout << '\n';
  98.     }
  99.     return 0;
  100. }
RAW Paste Data