//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