01204212/river crossing puzzle

This is part of 01204212

Code

Graph

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Graph {

    private int n;
    private int m;
    private ArrayList<Integer>[] adjList;
    
    @SuppressWarnings("unchecked")
    public Graph(int n) {
        this.n = n;
        m = 0;
        
        adjList = (ArrayList<Integer>[]) new ArrayList[n];
        for(int i=0; i<n; i++) {
            adjList[i] = new ArrayList<Integer>();
        }
    }

    public int getN() {
        return n;
    }
    
    public int getM() {
        return m;
    }
    
    public void addArc(int u, int v) {
        adjList[u].add(v);
        m++;
    }
    
    public void addEdge(int u, int v) {
        adjList[u].add(v);
        adjList[v].add(u);
        m += 2;
    }
    
    public int degree(int u) {
        return adjList[u].size();
    }
    
    public ListIterator<Integer> iterator(int u) {
        return adjList[u].listIterator();
    }
    
    public List<Integer> getAdjList(int u) {
        return adjList[u];
    }
}

Main for w,g,c

import java.util.ArrayList;
import java.util.List;

public class Main {
    Graph g;

    int[] levels;
    int[] parents;
    
    public static void main(String[] args) {
        Main main = new Main();
        
        main.process();
    }

    private void process() {
        buildGraph();
        State startingState = new State(State.LEFT, State.LEFT,
                State.LEFT,State.LEFT);
        State finalState = new State(State.RIGHT, State.RIGHT,
                State.RIGHT,State.RIGHT);
        breadthFirstSearch(startingState.getId());
        
        int v = finalState.getId();
        while(true) {
            State s = State.createFromId(v);
            System.out.println(s);
            v = parents[v];
            if(v == -1) {
                break;
            }
        }
        System.out.println();
    }

    private void buildGraph() {
        g = new Graph(3000);
        for(int i=0; i<3000; i++) {
            State s = State.createFromId(i);
            if(s.isValidState() && s.isOk()) {
                List<State> nextStates = s.getNextStates();
                
                for(State ns : nextStates) {
                    g.addArc(i, ns.getId());
                }
            }
        }
    }    

    void breadthFirstSearch(int s) {
        List<Integer> nextLevel = new ArrayList<Integer>();
        levels = new int[g.getN()];
        parents = new int[g.getN()];
        
        for(int u=0; u < g.getN(); u++) {
            levels[u] = -1;
            parents[u] = -1;
        }
        levels[s] = 0;
        nextLevel.add(s);
        
        while(! nextLevel.isEmpty()) {
            List<Integer> currentLevel = nextLevel;
            nextLevel = new ArrayList<Integer>();

            for(int u : currentLevel) {
                for(int v : g.getAdjList(u)) {
                    if(levels[v] == -1) {
                        levels[v] = levels[u] + 1;
                        parents[v] = u;
                        nextLevel.add(v);
                    }
                }
            }
        }
    }
}

State class for wolf, goat, cabbage game

import java.util.LinkedList;
import java.util.List;

public class State {
    static final int LEFT = 1;
    static final int RIGHT = 2;
    
    public int wolf;
    public int goat;
    public int cabbage;
    public int boat;
    
    public State(int w, int g, int c, int b) {
        wolf = w;
        goat = g;
        cabbage = c;
        boat = b;
    }

    public int opposite(int bank) {
        if(bank == LEFT) {
            return RIGHT;
        } else {
            return LEFT;
        }
    }

    public boolean isVariableValid(int v) {
        return (v == LEFT) || (v == RIGHT);
    }
    
    public boolean isValidState() {
        return isVariableValid(wolf) && isVariableValid(goat) &&
                isVariableValid(cabbage) && isVariableValid(boat);
    }

    public boolean isOk() {
        if(!isValidState()) {
            return false;
        }

        if((wolf == goat) && (boat != goat)) 
            return false;
        
        if((goat == cabbage) && (boat != cabbage))
            return false;
        
        return true;
    }
    
    public int getId() {
        return 1000 * wolf + 100 * goat + 10 * cabbage + boat; 
    }
    
    static public State createFromId(int id) {
        int w = id / 1000;
        int g = (id % 1000) / 100;
        int c = (id % 100) / 10;
        int b = id % 10;
        
        return new State(w,g,c,b);
    }
    
    List<State> getNextStates() {
        LinkedList<State> allStates = new LinkedList<State>();         
        
        allStates.add(new State(wolf, goat, cabbage, opposite(boat)));
        if(wolf == boat) {
            allStates.add(new State(opposite(wolf), goat, cabbage, 
                    opposite(boat)));
        }
        if(goat == boat) {
            allStates.add(new State(wolf, opposite(goat), cabbage, 
                    opposite(boat)));            
        }
        if(cabbage == boat) {
            allStates.add(new State(wolf, goat , opposite(cabbage), 
                    opposite(boat)));            
        }

        LinkedList<State> states = new LinkedList<State>();         
        for(State s : allStates) {
            if(s.isOk()) {
                states.add(s);
            }
        }
        return states;
    }
    public String toString() {
        String bl = "";
        String br = "";
        
        if(wolf == LEFT) {
            bl += "W ";
            br += "  ";
        } else {
            bl += "  ";
            br += "W ";            
        }
        if(goat == LEFT) {
            bl += "G ";
            br += "  ";
        } else {
            bl += "  ";
            br += "G ";            
        }
        if(cabbage == LEFT) {
            bl += "C ";
            br += "  ";
        } else {
            bl += "  ";
            br += "C ";            
        }

        if(boat == LEFT) {
            return bl + "| B         | " + br;
        } else {
            return bl + "|         B | " + br;
        }
    }
}