(UVA) Getting Gold - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2597

For this problem, if the player reaches a position that is next to a trap, the only safe solution is to go back to the old position. Due to this fact, the solution below is using the Depth-First Search.


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

class Main {
    public static int numRows;
    public static int numCols;
    public static char[][] matrix;
    public static boolean[][] visited;
    public static int[] vi = {-1,0,0,1};
    public static int[] vj = {0,-1,1,0};
    public static int countGold;
       
    public static boolean isSafe(int currI, int currJ) {
        for (int i = 0; i < 4; i++) {
            int nextI = currI+vi[i];
            int nextJ = currJ+vj[i];
            if (matrix[nextI][nextJ] == 'T') {
                return false;
            }
        }
       
        return true;
    }
   
    public static void dfs(int currI, int currJ) {
        if (currI < 0 || currJ < 0 || currI >= numRows || currJ >= numCols || matrix[currI][currJ] == '#' || visited[currI][currJ]) {
            return;
        }
       
        if (matrix[currI][currJ] == 'G') {
            countGold++;
        }
        visited[currI][currJ] = true;
       
        if (!isSafe(currI, currJ)) {
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nextI = currI+vi[i];
            int nextJ = currJ+vj[i];
            dfs(nextI, nextJ);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        while (sc.hasNext()) {
            numCols = sc.nextInt();
            numRows = sc.nextInt();
            matrix = new char[numRows][numCols];
            int startI = 0;
            int startJ = 0;
            for (int i = 0; i < numRows; i++) {
                String line = sc.next();
                for (int j = 0; j < numCols; j++) {
                    matrix[i][j] = line.charAt(j);
                    if (matrix[i][j] == 'P') {
                        startI = i;
                        startJ = j;
                    }
                }
            }
           
            countGold = 0;
            visited = new boolean[numRows][numCols];
            dfs(startI, startJ);
            System.out.println(countGold);
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}