Solução Preso no Castelo

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: