Advertisement
NAbdulla

Switch bulbs

Jul 31st, 2015
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.62 KB | None | 0 0
  1. /****************************************************************************************
  2.    *  Md. Abdulla Al Mamun (Nayon)
  3.    *  ID: 1306001
  4.    *  Session: 2013-2014
  5.    *  Department of Computer Science and Engineering
  6.    *  Begum Rokeya University, Rangpur (BRUR)
  7.    *
  8.    *  Project Name:         Switch Bulbs
  9.    *  File Created on:      Monday, 2015-07-27-23.45.30
  10.    *  Current File:         D:\My Codes\C and C++\Code-Blocks Projects\Switch Bulbs\main.cpp
  11.    *  Language:             English (U.S.)
  12.    *  Encoding:             windows-1252
  13. *****************************************************************************************/
  14. #include <iostream>
  15. #include <string>
  16. #include <algorithm>
  17. #include <vector>
  18. #include <queue>
  19. #include <map>
  20. #include <cstdio>
  21. #include <cstdlib>
  22. #include <cmath>
  23. #include <cstring>
  24.  
  25. using namespace std;
  26.  
  27. #define EPS 1e-9
  28. #define MAX 32768
  29.  
  30. bool isEqual(double a, double b)
  31. {
  32.     return abs(a - b) < EPS;
  33. }
  34.  
  35. int m;
  36. vector<int> connections[45];
  37. int bfs(char* str)
  38. {
  39.     int visited[MAX+5];
  40.     int level[MAX+5];
  41.     queue<int>Q;
  42.     char *ptr;
  43.     int start = 0, destination = (int)strtol(str, &ptr, 2);
  44.  
  45.     memset(visited, 0, sizeof(visited));
  46.     Q.push(start);
  47.     visited[start] = 1;
  48.     level[start] = 0;
  49.  
  50.     while(!Q.empty()){
  51.         int par = Q.front();
  52.         Q.pop();
  53.  
  54.         for(int i = 0; i < m; i++){//switches 0 to m-1
  55.             int current = par;
  56.             int s = connections[i].size();//number of connected number of bulbs with i th switch
  57.             for(int j = 0; j < s; j++){
  58.                 int tog = connections[i][j];
  59.                 current ^= (1 << tog);//toggling the tog th bit;
  60.             }
  61.             if(visited[current] == 0){
  62.                 visited[current] = 1;
  63.                 level[current] = level[par] + 1;
  64.                 if(current == destination)return level[current];
  65.                 else Q.push(current);
  66.             }
  67.         }
  68.     }
  69.     return -1;
  70. }
  71.  
  72. int main()
  73. {
  74.     //freopen("in.txt", "r", stdin);
  75.     int t, n, i, j, k, q;
  76.     char dest[20];
  77.  
  78.     scanf("%d", &t);
  79.     for(int t1 = 1; t1 <= t; t1++){
  80.         scanf("%d %d", &n, &m);
  81.         for(i = 0; i < m; i++){
  82.             scanf("%d", &k);
  83.             while(k--){
  84.                 scanf("%d", &j);
  85.                 connections[i].push_back(j);//j th bulb is toggled by i th switch
  86.             }
  87.         }
  88.         scanf("%d", &q);
  89.         printf("Case %d:\n", t1);
  90.         while(q--){
  91.             scanf("%s", dest);
  92.  
  93.             printf("%d\n", bfs(dest));
  94.         }
  95.         printf("\n");
  96.         for(i = 0; i < m; i++)
  97.             connections[i].clear();
  98.     }
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement