Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /****************************************************************************************
- * Md. Abdulla Al Mamun (Nayon)
- * ID: 1306001
- * Session: 2013-2014
- * Department of Computer Science and Engineering
- * Begum Rokeya University, Rangpur (BRUR)
- *
- * Project Name: Switch Bulbs
- * File Created on: Monday, 2015-07-27-23.45.30
- * Current File: D:\My Codes\C and C++\Code-Blocks Projects\Switch Bulbs\main.cpp
- * Language: English (U.S.)
- * Encoding: windows-1252
- *****************************************************************************************/
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <map>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- using namespace std;
- #define EPS 1e-9
- #define MAX 32768
- bool isEqual(double a, double b)
- {
- return abs(a - b) < EPS;
- }
- int m;
- vector<int> connections[45];
- int bfs(char* str)
- {
- int visited[MAX+5];
- int level[MAX+5];
- queue<int>Q;
- char *ptr;
- int start = 0, destination = (int)strtol(str, &ptr, 2);
- memset(visited, 0, sizeof(visited));
- Q.push(start);
- visited[start] = 1;
- level[start] = 0;
- while(!Q.empty()){
- int par = Q.front();
- Q.pop();
- for(int i = 0; i < m; i++){//switches 0 to m-1
- int current = par;
- int s = connections[i].size();//number of connected number of bulbs with i th switch
- for(int j = 0; j < s; j++){
- int tog = connections[i][j];
- current ^= (1 << tog);//toggling the tog th bit;
- }
- if(visited[current] == 0){
- visited[current] = 1;
- level[current] = level[par] + 1;
- if(current == destination)return level[current];
- else Q.push(current);
- }
- }
- }
- return -1;
- }
- int main()
- {
- //freopen("in.txt", "r", stdin);
- int t, n, i, j, k, q;
- char dest[20];
- scanf("%d", &t);
- for(int t1 = 1; t1 <= t; t1++){
- scanf("%d %d", &n, &m);
- for(i = 0; i < m; i++){
- scanf("%d", &k);
- while(k--){
- scanf("%d", &j);
- connections[i].push_back(j);//j th bulb is toggled by i th switch
- }
- }
- scanf("%d", &q);
- printf("Case %d:\n", t1);
- while(q--){
- scanf("%s", dest);
- printf("%d\n", bfs(dest));
- }
- printf("\n");
- for(i = 0; i < m; i++)
- connections[i].clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement