Solução Caça ao Tesouro

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Vamos salvar uma matriz de nome mapa para representar o plano da ilha. Note que a distância entre os pontos Aem passos do pirato é o valor de \mid A_x-B_x\mid +\mid A_y-B_y \mid. Assim, para cada pista, vamos percorrer todas as posições do mapa procurando pelas que estão à distância indicada da posição em que está a pista. Para cada posição (i, j) dessas encontrada, somamos uma unidade em mapa[i][j], indicando que encontramos mais uma pista que pode se referir a essa posição. Depois de lida a entrada, cada posição de mapa guarda quantas pistas podem se referir a ela. A verdadeira localização do tesouro deve ser apontada por todas as k pistas da entrada, logo, vamos salvar em um vector de pair<int,int> todas as posições (i, j) cujo valor de mapa[i][j] é exatamente k. Se após percorrermos todo o mapa houver apenas uma posição dessas, ela é a resposta, caso contrário, não temos certeza onde está o tesouro e devemos imprimir uma única linha, com os inteiros -1 -1. Segue o código para melhor entendimento:

Nosso leitor Roger Benet também apresentou uma solução que responde corretamente ao problema, usando uma ideia semelhante:

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