(UVA) Marcus - Solution

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

Although this problem is related to the Depth-First Search (DFS), it does not go as far as possible before backtracking. Instead, it follows the rule about the letters in 'IEHOVA'.


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

class Main {
    public static int numRows;
    public static int numCols;
    public static int startI;
    public static int startJ;
    public static char[][] matrix;
    public static String safe = "@IEHOVA#";
    public static ArrayList<String> commands;
    public static ArrayList<String> answer;
    public static int[] vi = {-1,0,0};
    public static int[] vj = {0,-1,1};
    public static String[] directions = {"forth","left","right"};
   
    public static void rec(int currI, int currJ, int step) {
        if (currI < 0 || currJ < 0 || currI >= numRows || currJ >= numCols || safe.indexOf(matrix[currI][currJ]) != step) {
            return;
        }
        if (matrix[currI][currJ] == '#') {
            answer = (ArrayList<String>) commands.clone();
            return;
        }
       
        for (int i = 0; i < 3; i++) {
            commands.add(directions[i]);
            rec(currI+vi[i], currJ+vj[i], step+1);
            commands.remove(commands.size()-1);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            numRows = sc.nextInt();
            numCols = sc.nextInt();
            matrix = new char[numRows][numCols];
            for (int j = 0; j < numRows; j++) {
                String line = sc.next();
                for (int k = 0; k < numCols; k++) {
                    matrix[j][k] = line.charAt(k);
                    if (matrix[j][k] == '@') {
                        startI = j;
                        startJ = k;
                    }
                }
            }
           
            commands = new ArrayList<>();
            answer = new ArrayList<>();
            rec(startI, startJ, 0);
           
            for (int j = 0; j < answer.size()-1; j++) {
                System.out.print(answer.get(j) + " ");
            }
            System.out.println(answer.get(answer.size()-1));
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}