Solução Caça ao Tesouro

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:


#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 110
typedef pair<int,int> ii;
int n, k, mapa[MAXN][MAXN];
vector<ii> resp;
int main(){
scanf("%d %d", &n, &k); // leio os valores de n e k
// para cada pista
for(int i=1; i<=k; i++){
// declaro e leio os valores de x, y e d
int x, y, d;
scanf("%d %d %d", &x, &y, &d);
// e marco todas as posições que satisfazem às condições
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(abs(x-i)+abs(y-j)==d) mapa[i][j]++;
}
// guardo todas as casas qe foram apontadas em todas as pistas
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(mapa[i][j]==k) resp.push_back(ii(i, j));
// se houver exatamente uma casa possível, imprimo suas coordenadas
if(resp.size()==1) printf("%d %d\n", resp[0].first, resp[0].second);
// caso contrário, imprimo uma linha com os números -1 -1
else printf("-1 -1\n");
return 0;
}

view raw

tesouro.cpp

hosted with ❤ by GitHub

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


#include <cstdio>
#include <algorithm>
#define MAX 110
using namespace std;
int mapa[MAX][MAX];
int n,k;
int main(){
scanf("%d %d", &n, &k);
for(int i = 0; i < k; i++){
int a,b,c,sa,sb,cont;
scanf("%d %d %d", &a, &b, &c);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if( abs(i-a) + abs(j-b) == c ){
mapa[i][j]++;
}
}
}
}
bool ver = false;
int x = -1,y = -1;
for(int i = n-1; i > -1; i--){
for(int j = n-1; j > -1; j--){
if(mapa[i][j] == k){
if(x != -1){
ver = true;
break;
}
x = i;
y = j;
}
}
}
if(ver == false)printf("%d %d\n",x,y);
else printf("-1 -1\n");
return 0;
}