Monday, December 26, 2016

UVa 10507 - Waking up brain

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

No comments:

Post a Comment