(SPOJ) Setas - Solution

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

The solution below uses a Depth-First Search to solve this problem. In this method, every position that is valid is replaced by the character '*', and every position that is considered invalid is replaced by '#'. In the end, we only need to count how many '*' we have in our matrix.


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

class solucao {
    public HashMap<Character, Integer> map;
    public char[][] matrix;
    public boolean[][] visited;
    public int size;
    public int[] vi = {-1,0,0,1};
    public int[] vj = {0,-1,1,0};
   
    public char dfs(int currI, int currJ) {
        if (currI < 0 || currJ < 0 || currI >= size || currJ >= size  || matrix[currI][currJ] == '#') {
            return '#';
        }
        if (visited[currI][currJ] || matrix[currI][currJ] == '*') {
            return '*';
        }
       
        visited[currI][currJ] = true;
        int nextI = currI + vi[map.get(matrix[currI][currJ])];
        int nextJ = currJ + vj[map.get(matrix[currI][currJ])];
        matrix[currI][currJ] = dfs(nextI, nextJ);
       
        return matrix[currI][currJ];
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        map = new HashMap<>();
        map.put('A', 0);
        map.put('<', 1);
        map.put('>', 2);
        map.put('V', 3);
       
        String line = br.readLine();
        size = Integer.parseInt(line);
       
        matrix = new char[size][size];
        for (int i = 0; i < size; i++) {
            line = br.readLine();
            for (int j = 0; j < size; j++) {
                matrix[i][j] = line.charAt(j);
            }
        }
       
        visited = new boolean[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (matrix[i][j] == '*' || matrix[i][j] == '#') {
                    continue;
                }
                char c = dfs(i, j);
            }
        }
       
        int countValid = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (matrix[i][j] == '*') {
                    countValid++;
                }
            }
        }
       
        bw.write(countValid+"\n");
           
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        solucao m = new solucao();
        m.process();
       
        System.exit(0);
    }
}