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