Esta questão é um knapsack clássico sem alterações, onde a quantidade H de
horas que Juliana possui é capacidade da mochila. E os itens são dados com
peso T e valor R na entrada.
Esta questão pode ser resolvida com um DFS em um grafo implícito. Neste grafo, o nó é como o tabuleiro está no momento, ou seja, um possível nó seria:
101
010
101
Para representar este nó você pode usar uma string, ou um bitset, ou int.
As arestas do grafo são formadas pelos movimentos possíveis para sair de um estado
para outro. Cada estado tem 9 arestas, pois todo estado você pode fazer 9
movimentos, que seria clicar em cada um dos quadrados, no tabuleiro 3x3.
Então, para realizar a travessia nesse grafo, para cada casa no tabuleiro você
deveria executar o movimento e prosseguir com o DFS. E como o grafo é implícito
e você não sabe quantos nós tem a princípio, para marcar quais foram visitados
ou não, você pode usar um set que guarda os estados já visitados.
Esta questão pode ser solucionada de diversas formas, o importante é a solução
ter complexidade O(n log n). Um dos jeitos de resolver ela, é colocar todos
os nomes em um set, e utilizar o count do set para saber se o nome está lá
ou não.
Outro jeito de resolver é guardar os nomes em um vector<string> e utilizar
a função binary_search para saber se o nome está ou não no vector.
Nesta questão Laura precisa saber o menor caminho para cada cidade, partindo
da cidade dela, a cidade 1. Para conseguir isso, você pode utilizar o
algoritmo de Dijkstra, sem modificações. Ao final do algoritmo, o array de
distâncias vai guardar menor distancia entre 1 e as outras cidades.
Toda cidade que não tiver distância infinita, quer dizer que Laura consegue
alcançar. Estas devem ser colocadas em um vector<pair<int, int>>, onde
o primeiro elemento do par é a distância e o segundo é o número da cidade.
Este vector deve ser ordenado, e após a ordenação você terá as cidades na ordem
de visita correta.
Esta questão conceitua um tipo de grafo, chamado de grafo bipartido. Um grafo bipartido é onde todo vizinho de um nó tem uma cor oposta a esse nó. Para descobrir se dado um grafo ele é bipartido ou não, você pode utilizar uma variação do BFS. Onde você vai utilizar o array de visitados, não só marcando com 0 para não visita e 1 para visitado, mas com 3 valores possíveis.
0-> não visitado1-> visitado e tem opinião A-1-> visitado e tem opinião B
Assim, caso um vizinho seu já tenha sido visitado, ou seja, ele é 1 ou -1.
Ele deve ter um valor oposto ao seu, caso ele tenha o mesmo valor que o seu,
você deve marcar esse grafo como não sendo bipartido.