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 A e B em passos do pirato é o valor de 
. 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Nosso leitor Roger Benet também apresentou uma solução que responde corretamente ao problema, usando uma ideia semelhante:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |