Solução Preso no Castelo

Solução por Rogério Júnior

Este problema é feito usando-se uma única BFS, com um apequena modificação. Se você não sabe o que é BFS, clique aqui para ver a aula do Curso Noic sobre algoritmos de Flood Fill. Para começarmos o problema, vamos ler a entrada, salvando as chaves no array de vectors de nome key (key[i] é um vetor com os números das salas que pode ser aberta com as chaves encontradas na sala i) e o grafo em uma lista de adjacências, o array de vectors de int de nome lista. Basta agora implementarmos a BFS modificada que irá retornar true caso possamos visitar todas as salas do castelo e false, caso contrário.

Além do vetor marcado que guardará as salas não visitadas, teremos o vetor forb que guardará as salas que ainda não podemos visitar po não termos a chave (se forb[i]==true, não tenho a chave da sala i). Para iniciarmos o loop da BFS, salvamos que não temos nenhuma chave exceto a da sala 1, a marcamos como visitada e a colocamos na fila da BFS. Agora, como no algoritmo comum, salvo a próxima sala da fila em um inteiro davez e a tiro da fila. Se eu não tiver sua chave, devo reinseri-la no final da fila, pois pode ser que encontremos sua chave posteriormente, e só então poderemos abri-la, logo, não devemos tirá-la da fila de salas acessíveis. Se eu já tiver a chave de davez, executo normalmente a BFS, adicionando seus vizinhos não marcados à fila e guardando, em marcado, que já foram visitados, lembrando apenas de olhar as chaves encontradas nessa sala (no vector key[davez]) e salvar que são todas acessíveis, usando um for para marcar false em suas respectivas posições do vetor forb.

Entretanto, se não for possível que visitemos todas as salas, o programa descrito até aqui poderá entrar em loop infinito. Note que que se é impossível chegar a uma sala porque não tenho sua chave, ela nunca sairá da fila (pois sempre a reinsiro essa sala no final da fila) e o loop nunca acaba. Portanto, só preciso continuar a BFS enquanto houver salas na fila que posso visitar (já tenho a chave), pois se ficarem apenas salas inacessíveis, devo será impossível abri-las e a BFS deve retornar false.

Note que, se houver apenas salas inacessíveis na fila, a BFS irá percorrer todas, uma a ma, retirando e reinserindo-as na fila. Caso isso ocorra, ela deve retornar false. Para identificarmos se isso ocorreu, basta que, sempre que reinserirmos alguém na fila, salvarmos qual sala foi a primeira a ser reinserida em uma variável first. Assim , se a BFS continuar, percorrer toda a fila, e o primeiro voltar a ser o primeiro elemento reinserido, devemos retornar false. No entanto, se encontrarmos uma única sala que podemos acessar (que já temos a chave), então não precisaremos fazer essa checagem (pois ela busca saber se todas as salas da fila são inacessíveis) e reiniciamos o valor de first para zero, pois não há salas com esse número. Note que para sempre mantermos a primeira sala que é inacessível em first, basta que só a atualizemos se ela estiver com seu valor inicial zero.

Terminado o loop da BFS, basta verificar se todas as salas foram visitadas. Para isso basta salvarmos uma variável count, de valor inicial zero, e adicionarmos uma unidade a seu valor sempre que visitamos uma sala nova. No fim da BFS, retornamos true se o número de salas visitadas count for igual ao número de salas n, retornando false caso contrário. Segue o código para melhor entendimento:

	#include <cstdio>
	#include <cstring>
	#include <vector>
	#include <queue>

	#define MAXN 1010

	using namespace std;

	vector<int> lista[MAXN];
	vector<int> key[MAXN];

	bool forb[MAXN], marcado[MAXN];

	int n, m;

	// BFS modificada
	bool bfs(){

	queue<int> fila;

	fila.push(1);

	memset(forb, true, sizeof(forb));
	memset(marcado, false, sizeof(marcado));

	forb[1]=false;
	marcado[1]=true;

	int davez, tam, count=0,first=0;

	// loop principal
	while(!fila.empty()){

	// salvo a primeira sala da fila e a retiro dela
	davez=fila.front(); fila.pop();

	// se ainda não tenho a sua chave
	if(forb[davez]){

	// verifico se a BFS não acabou de percorrer todas as salas da fila
	// e nenhuma delas era acessível. Se isso ocorrer, a BFS retorna false
	if(davez==first) return false;

	// caso contrário, reinsiro a sala no fim da fila
	fila.push(davez);

	// e se ela for a primeira sala de uma sequência a ser reinserida
	// salvo seu número em first
	if(!first) first=davez;

	// e continuo para a próxima repetição do for
	continue;
	}

	// se posso acessar a sala, então first recebe zero
	// pois achei uma sala na fila que é acssível
	first=0;

	// aumento o número de salas que posso visitar
	count++;

	// e olho todas as chaves encontradas na sala,
	// salvando, com false em forb, que elas são agora acessíveis
	tam=key[davez].size();
	for(int i=0; i<tam; i++) forb[key[davez][i]]=false;

	// e como em uma BFS normal, procuro por vizinhos ainda não visitados
	// os marco e adiciono na fila
	tam=lista[davez].size();

	for(int i=0; i<tam; i++) if(!marcado[lista[davez][i]]){

	fila.push(lista[davez][i]);
	marcado[lista[davez][i]]=true;
	}
	}

	// por fim, se tiver visitado todas as salas, a BFS retorna true
	return count==n;
	}

	int main(){

	// processo todos os casos de entrada até fim de arquivo
	while(scanf("%d %d", &n, &m)!=EOF){

	// reinicio os arrays do programa
	for(int i=0; i<=n; i++){

	lista[i].clear();
	key[i].clear();
	}

	// leio o grafo e o salvo na lista de adjacências
	int a, b;
	for(int i=0; i<m; i++){

	scanf("%d %d", &a, &b);

	lista[a].push_back(b);
	lista[b].push_back(a);
	}

	// depois leio onde está a chave da cada sala
	for(int i=2; i<=n; i++) {

	scanf("%d", &a);
	key[a].push_back(i);
	}

	// por fim, se a bfs retornar true, então posso visitar todas as salas
	if(bfs()) printf("sim\n");

	// caso contrário, não posso
	else printf("nao\n");
	}
	return 0;
	}

view raw

castelo.cpp

hosted with ❤ by GitHub