(UVA) Playing with Wheels - Solution

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

The problem asks us if it is possible to go from a state to another one without visiting states that are forbidden using the minimum number of operations. For this reason, the solution below used Breadth-First Search (BFS) to solve this problem.


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

class Main {
    public int[][] forbidden;
    public int numForbidden;
    public int[] start;
    public int[] end;
   
    public int bfs(int s1, int s2, int s3, int s4) {
        Queue<State> queue = new ArrayDeque<>();
        queue.add(new State(s1, s2, s3, s4, 0));
      
        boolean[][][][] visited = new boolean[10][10][10][10];
        for (int i = 0; i < numForbidden; i++) {
            visited[forbidden[i][0]][forbidden[i][1]][forbidden[i][2]][forbidden[i][3]] = true;
        }
      
        while (queue.size() > 0) {
            State curr = queue.poll();
            int currS1 = curr.s1;
            int currS2 = curr.s2;
            int currS3 = curr.s3;
            int currS4 = curr.s4;
            int currNumOp = curr.numOp;
          
            if (visited[currS1][currS2][currS3][currS4]) {
                continue;
            }
            visited[currS1][currS2][currS3][currS4] = true;
          
            if (currS1 == end[0] && currS2 == end[1] && currS3 == end[2] && currS4 == end[3]) {
                return currNumOp;
            }
          
            queue.add(new State((currS1+1)%10, currS2, currS3, currS4, currNumOp+1));
            queue.add(new State(currS1, (currS2+1)%10, currS3, currS4, currNumOp+1));
            queue.add(new State(currS1, currS2, (currS3+1)%10, currS4, currNumOp+1));
            queue.add(new State(currS1, currS2, currS3, (currS4+1)%10, currNumOp+1));
            queue.add(new State(((currS1-1)+10)%10, currS2, currS3, currS4, currNumOp+1));
            queue.add(new State(currS1, ((currS2-1)+10)%10, currS3, currS4, currNumOp+1));
            queue.add(new State(currS1, currS2, ((currS3-1)+10)%10, currS4, currNumOp+1));
            queue.add(new State(currS1, currS2, currS3, ((currS4-1)+10)%10, currNumOp+1));
        }
      
        return -1;
    }
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = sc.nextInt();
        for (int test = 0; test < numTests; test++) {
            start = new int[4];
            end = new int[4];
            for (int i = 0; i < 4; i++) {
                start[i] = sc.nextInt();
            }
            for (int i = 0; i < 4; i++) {
                end[i] = sc.nextInt();
            }
          
            numForbidden = sc.nextInt();
            forbidden = new int[numForbidden][4];
            for (int i = 0; i < numForbidden; i++) {
                for (int j = 0; j < 4; j++) {
                    forbidden[i][j] = sc.nextInt();
                }
            }
          
            bw.write(bfs(start[0], start[1], start[2], start[3])+"\n");
        }
                                             
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}

class State {
    int s1;
    int s2;
    int s3;
    int s4;
    int numOp;
  
    public State(int s1, int s2, int s3, int s4, int numOp) {
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
        this.s4 = s4;
        this.numOp = numOp;
    }
}