Solução escrita por Estela Baron
Conhecimento prévio necessário:
Podemos observar que o conjunto de espaços e corredores caracterizam um grafo, sendo as galerias os vértices e os corredores as arestas.
Agora, vamos imaginar que os guardas consigam andar entre um espaço e outro por meio dos corredores. Observe que, se diminuirmos o alcance de sua "visão" em uma unidade toda vez que ele percorre um corredor, continuamos tendo o mesmo problema. Com isso, basta descobrir quais são os espaços alcançados pelos guardas. Cada guarda só consegue passar de uma sala para outra se o alcance for maior que zero (ele pode estar em um espaço com o alcance zero).
A partir disso, uma ideia possível é ver todas as posições que cada guarda alcança por meio de várias bfs ou dfs. No entanto, isso ficaria muito lento.
Por isso, uma solução possível é aplicar o algoritmo de Dijkstra com algumas modificações. Um fato importante é que, na existência de um guarda em um vértice, queremos maximizar o alcance restante. Assim, conseguimos alcançar mais espaços e cobrir uma área maior. Logo, diferentemente da aplicação original do algoritmo, vamos priorizar a análise/ o processamento dos vértices que têm o guarda com o maior alcance. Assim, é possível evitar operações desnecessárias.
Para cada vértice do topo da fila de prioridade, checamos se o maior alcance do vértice é maior que o alcance contido na fila. Se for, passamos para o próximo da fila. Caso contrário, percorremos todos os vértices adjacentes e vemos se o maior alcance do vizinho é menor que o alcance do vértice atual menos um. Se for, atualizamos o maior alcance do vizinho e adicionamos o vizinho e esse novo maior alcance na fila. Senão, passamos para o próximo vizinho.
Ao final, todos os espaços (vértices) que poderiam ser vigiados terão sido visitados. Portanto, verificamos, para cada vértice, se ele foi visitado. Com isso, basta imprimir a quantidade de espaços visitados e os números deles.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.