//UVa 10507 - Waking up brain #include <iostream> #include <map> #include <string.h> using namespace std; int numberOfNodes; string initialNodes; bool adj[26][26]; int levelOf[26]; int oo; void readAndFillAdjacencyMatrix() { int numberOfEdges; cin >> numberOfEdges; cin >> initialNodes; memset(adj, false, sizeof(adj)); for (int i = 0; i < numberOfEdges; i++) { string edge; cin >> edge; adj[edge[0] - 'A'][edge[1] - 'A'] = true; adj[edge[1] - 'A'][edge[0] - 'A'] = true; } } bool areAllNodesVisited() { int nodesVisited = 0; for (char node = 'A'; node <= 'Z'; node++) { if (levelOf[node - 'A'] != oo) nodesVisited++; } return nodesVisited == numberOfNodes; } int bfs() { memset(levelOf, 127, sizeof(levelOf)); oo = levelOf[0]; levelOf[initialNodes[0] - 'A'] = 0; levelOf[initialNodes[1] - 'A'] = 0; levelOf[initialNodes[2] - 'A'] = 0; bool thereAreChanges = true; int level = 0; while (thereAreChanges && !areAllNodesVisited()) { thereAreChanges = false; level++; for (char node = 'A'; node <= 'Z'; node++) if (levelOf[node - 'A'] == oo) { int visitedNeighbors = 0; for (char neighbor = 'A'; neighbor <= 'Z'; neighbor++) if (adj[node - 'A'][neighbor - 'A'] && levelOf[neighbor - 'A'] < level) visitedNeighbors++; if (visitedNeighbors >= 3) { levelOf[node - 'A'] = level; thereAreChanges = true; } } } return level; } int main() { while (cin >> numberOfNodes) { readAndFillAdjacencyMatrix(); int level = bfs(); bool allVisited = areAllNodesVisited(); if (allVisited) cout << "WAKE UP IN, " << level << ", YEARS" << endl; else cout << "THIS BRAIN NEVER WAKES UP" << endl; } return 0; }
Monday, December 26, 2016
UVa 10507 - Waking up brain
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment