(SPOJ) Caça ao tesouro - Solution

Link to the problem: http://br.spoj.com/problems/TESOUR11/

For each clue that we have, we need to know all its possible ends. Moreover, in each possible end we keep a counter associated with how many clues move us to that position. Then, we know how to determine for sure where the treasure is if there is only one position where the counter is equal to the number of clues.


import java.io.*;
import java.util.*;

class Main {
    public int[] vi = {-1,0,0,1};
    public int[] vj = {0,-1,1,0};
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        String[] s = line.split("\\s");
        int size = Integer.parseInt(s[0]);
        int numClues = Integer.parseInt(s[1]);
       
        Clue[] clues = new Clue[numClues];
        for (int i = 0; i < numClues; i++) {
            line = br.readLine();
            s = line.split("\\s");
            int row = Integer.parseInt(s[0]);
            int col = Integer.parseInt(s[1]);
            int dist = Integer.parseInt(s[2]);
            clues[i] = new Clue(row, col, dist);
        }
       
        int countAnswer = 0;
        int answerRow = 0;
        int answerCol = 0;
        int[][] matrix = new int[size][size];
        for (int i = 0; i < numClues; i++) {
            Clue c = clues[i];
            int maxDist = c.dist;
           
            int[][] matrixTmp = new int[size][size];
            matrixTmp[c.row][c.col] = 0;
            int[][] visited = new int[size][size];
            visited[c.row][c.col] = 1;
           
            Queue<Coord> queue = new ArrayDeque<>();
            queue.add(new Coord(c.row, c.col));
            while (queue.size() > 0) {
                Coord coord = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int nextRow = coord.row+vi[j];
                    int nextCol = coord.col+vj[j];
                    if (nextRow < 0 || nextRow >= size || nextCol < 0 || nextCol >= size || visited[nextRow][nextCol] == 1) {
                        continue;
                    }
                   
                    visited[nextRow][nextCol] = 1;
                    matrixTmp[nextRow][nextCol] = matrixTmp[coord.row][coord.col]+1;
                    if (matrixTmp[nextRow][nextCol] == maxDist) {
                        matrix[nextRow][nextCol]++;
                        if (matrix[nextRow][nextCol] == numClues) {
                            answerRow = nextRow;
                            answerCol = nextCol;
                            countAnswer++;
                        }
                    }
                    else if (matrixTmp[nextRow][nextCol] < maxDist) {
                        queue.add(new Coord(nextRow, nextCol));
                    }
                }
            }   
        }

        if (countAnswer == 1) {
            System.out.println(answerRow + " " + answerCol);
        }
        else {
            System.out.println("-1 -1");
        }
       
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Clue {
    int row;
    int col;
    int dist;
   
    public Clue(int r, int c, int d) {
        row = r;
        col = c;
        dist = d;
    }
}

class Coord {
    int row;
    int col;
   
    public Coord(int r, int c) {
        row = r;
        col = c;
    }
}