Trouble with generating state space tree for maze solving with certain amount of powers

Currently I have an assignment where you are given a maze which consists of r x c Room. A room at the edges of the maze has walls representing the edges of the maze so you cannot traverse past the rooms at the edges.

The problem given is that you have been given the power to break walls in the maze and you can use it a given k times in the maze. The function public Integer pathSearch(int startRow, int startCol, int endRow, int endCol, int superpowers) is supposed to find the shortest path from the given starting point to the destination room.

There is also a need to keep track of the number of rooms reachable in a given shortest path number for the querying of numsReachable, which will return an integer indicating how many rooms there are such that the minimum number of steps required to reach it is k, based on your most recent pathSearch starting location.

My current idea is to generate a state space tree of a given starting room and power. Each vertex in the tree is represents a state which is a combination of the Room coordinates and the number of powers left. The edges of the tree represent a hop from one room to an adjacent room if there exists one.
If the adjacent room is separated by a wall, then the hop from the state of eg. Room (1,1) to Room (1,2) will result in a decrease in power.

Once I have generated the given tree, I would do a BFS on the tree and for every frontier at a given number of hops, I would keep it in a List at the given index representing number of hops, the frontier size representing the number of rooms reachable.

Here is the code for the recursive tree building.

private Maze maze;

// This set is to ensure there will be no repeated states in the state space tree
private Set<State> lookUp;

private List<Integer> shortest;// List of all rooms accessible at a current hop

private static final int NORTH = 0, SOUTH = 1, EAST = 2, WEST = 3;
private int[][] ddir = new int[][]{
		{-1, 0}, // North ddir[0]
		{1, 0},  // South ddir[1]
		{0, 1},  // East ddir[2]
		{0, -1}  // West ddir[3]
};

public MazeSolverWithPower() {
	maze = null;
}

@Override
public void initialize(Maze maze) {
	this.maze = maze;
	lookUp=null;
	shortest=null;
}`

	@Override
public Integer numReachable(int k) throws Exception {
	try{
		return shortest.get(k);
	} catch (Exception e) {
		return 0;
	}
}

@Override
public Integer pathSearch(int startRow, int startCol, int endRow,
						  int endCol, int superpowers) throws Exception {
	if (maze == null) {
		throw new Exception("Oh no! You cannot call me without initializing the maze!");
	}
	if (startRow < 0 || startCol < 0 || startRow >= maze.getRows() || startCol >= maze.getColumns() ||
			endRow < 0 || endCol < 0 || endRow >= maze.getRows() || endCol >= maze.getColumns()) {
		throw new IllegalArgumentException("Invalid start/end coordinate");
	}

	if (startCol == endCol && startRow == endRow) {
		maze.getRoom(startRow,startCol).onPath = true;
		return 0;
	}

	lookUp = new HashSet<>();
	GraphNode graph = build(new Pair(startRow,startCol, null), new Pair(endRow,endCol,null), superpowers);
	shortest = new ArrayList<>();
	boolean[][] visited = new boolean[maze.getRows()][maze.getColumns()];

	Pair destination = new Pair(endRow,endCol,null);

	List<GraphNode> frontier = new ArrayList<>();
	frontier.add(graph);
	
	// The return value: shortest path to destination
	int shortestPath = 0;
	// Tracks the number of hops currently.
	int currHops = 0;
	boolean found = false;

	// Breath First Search on state space graph
	while (frontier.size() > 0) {

		// List of all vertex in the next frontier
		List<GraphNode> next = new ArrayList<>();

		// At current frontier, this tracks all rooms reachable by in current hops
		shortest.add(currHops, frontier.size());

		// Iterate through the current frontier
		for (int i = 0; i < frontier.size(); i++) {
			GraphNode thisNode = frontier.get(i);
			State thiState = thisNode.state;
			Pair thisPair = thiState.pair; // Parent pair; for backtracking
			visited[thisPair.row][thisPair.col] = true;
			// End room found; Update the shortest path to end room;
			if (!found && thisPair.equals(destination)) {
				shortestPath = currHops;
				found = true;
				backTrack(thisPair);
			}
			// All neighbours of this current state
			// Iterate through the current node's adjacent nodes in the frontier
			for (GraphNode child : thisNode.adjacent) {
				// Getting the next frontier from all adjacent states of current state
				// This is the current room in the next frontier;
				Pair currRoom = child.state.pair;
				if (!visited[currRoom.row][currRoom.col]) {
                    visited[currRoom.row][currRoom.col] = true;
					child.state.pair = new Pair(currRoom.row, currRoom.col,thisPair);
					next.add(child);
				}
			}

		}
		currHops++;
		frontier = next;
	}

	return shortestPath == 0 ? null : shortestPath;
}

private void backTrack(Pair p) {
	Pair curr = p;
	while (curr!=null) {
		maze.getRoom(curr.row, curr.col).onPath = true;
		curr = curr.parent;
	}
}

private Room roomOf(Pair p) {
	return maze.getRoom(p.row, p.col);
}

private boolean canGo(Room room, int dir) {
	switch (dir) {
		case NORTH:
			return !room.hasNorthWall();
		case SOUTH:
			return !room.hasSouthWall();
		case EAST:
			return !room.hasEastWall();
		case WEST:
			return !room.hasWestWall();
		default:
			return false;
	}
}

private GraphNode build(Pair start, Pair end, int powers) {
	State startState = new State(start, powers);
	GraphNode graph = new GraphNode(startState);
	lookUp.add(startState);
	build(graph);
	return graph;
}


`private void build(GraphNode graph) {
	Queue<GraphNode> frontier = new LinkedList<>();
	frontier.add(graph);

	while (frontier.size() >= 1) {
		GraphNode v = frontier.poll();
		State currentState = v.state;
		int currPower = currentState.powersLeft;
		Pair p = currentState.pair;
		Room room = roomOf(p);
		if (currPower > 0) {
			for (int dir = NORTH; dir < 4; dir++) {
				Pair ajRoom = new Pair(p.row + ddir[dir][0], p.col + ddir[dir][1], null);
				if (canGo(room, dir)) {
					// Conserve power
					State newState = new State(ajRoom, currPower);
					if (lookUp.add(newState)) {
						GraphNode newV = new GraphNode(newState);
						v.adjacent.add(newV);
						frontier.add(newV);
					}
				} else {
					// Make sure you are not blasting out of the maze
					if (!isInvalid(ajRoom)) {
						// Use power to reach this room
						State newState = new State(ajRoom, currPower - 1);
						if (lookUp.add(newState)) {
							GraphNode newV = new GraphNode(newState);
							v.adjacent.add(newV);
							frontier.add(newV);
						}
					}
				}
			}
		} else {
			// Out of powers
			for (int dir = NORTH; dir <4; dir++) {
				Pair ajRoom = new Pair(p.row + ddir[dir][0], p.col + ddir[dir][1], null);
				if (canGo(room, dir)) {
					State newS = new State(ajRoom, 0);
					if (lookUp.add(newS)) {
						GraphNode newV = new GraphNode(newS);
						v.adjacent.add(newV);
						frontier.add(newV);
					}
				}
			}
		}
	}
}
private class GraphNode {
	State state;
	List<GraphNode> adjacent;
	GraphNode(State state) {
		this.state = state;
		adjacent = new ArrayList<>();
	}
}

// State consists of the room (represented by a coordinate pair) and
// the number of powers left.
private class State {
	Pair pair;
	int powersLeft;

	State(Pair p, int powers){
		this.pair = p;
		this.powersLeft = powers;
	}

	@Override
	public int hashCode() {
		return Objects.hash(this.pair.hashCode(), powersLeft);
	}

	@Override
	public boolean equals(Object other) {
		if (other instanceof State) {
			return ((State) other).pair.equals(this.pair) &&
					((State) other).powersLeft == this.powersLeft;
		} else {
			return false;
		}
	}

	@Override
	public String toString() {
		return "State: " + pair.toString() + " : " + powersLeft;
	}
}

private class Pair {
	// Coordinate pair;
	int row;
	int col;

	// This is for backtracking purpose to print out the path
	Pair parent;

	Pair (int r, int c, Pair parent) {
		row = r;
		col = c;
		this.parent = parent;
	}

	@Override
	public int hashCode() {
		int prime = 0x01000193;
		int offset = 0x811c9dc5;
		offset *= prime;
		offset ^= row;
		offset *= prime;
		offset ^= col;
		return offset;
	}

	@Override
	public boolean equals(Object other) {
		if (! (other instanceof Pair)) {
			return false;
		} else {
			return ((Pair) other).row == this.row &&
					((Pair) other).col == this.col;
		}
	}

	@Override
	public String toString() {
		return String.format("[%d, %d]", row, col);
	}
}

I am throwing the wrong number of rooms most likely because my building of the tree isn't functioning properly. Yet after testing for a few days I still could not find the error in my logic or code. Is there any insight on what could be done to change it?

Edit: For the pathSearch it will return the shortest path from the starting room to the destination room.

If the return value is:

1. 0 - destination is the starting location
2. null - indicates the destination is not reachable by any path given the number of powers

For the method numsReachable it is to return all possible rooms reachable in exactly the number of hops specified. If the number of hops exceed the maximum number of minimum hops needed to reach every room, then it will return 0;

Given this maze:

 - ┏━━━┳━━━━━━━┳━━━┳━━━┓
 - ┃   ┃       ┃   ┃ s ┃
 - ┃   ┃   ╻   ┃   ╹   ┃
 - ┃   ┃   ┃   ┃       ┃
 - ┣━━━╋━━━┻━━━╋━━━┓   ┃
 - ┃ d ┃       ┃   ┃   ┃
 - ┣━━━╋━━━┓   ┃   ┃   ┃
 - ┃   ┃   ┃   ┃   ┃   ┃
 - ┃   ┃   ┃   ┣━━━┛   ┃
 - ┃   ┃   ┃   ┃       ┃
 - ┗━━━┻━━━┻━━━┻━━━━━━━┛

Given a starting coordinate: Room at (0,4) indicated "s".

Destination: Room at (2,0)indicated "d".

Number of powers allowed: 2.

It takes 10 steps to reach d from s

However, the problem is that the number of rooms reachable given k steps is wrong.
This is my output:
Shortest path to d : null

• Steps 0 Rooms: 1
• Steps 1 Rooms: 2
• Steps 2 Rooms: 4
• Steps 3 Rooms: 6
• Steps 4 Rooms: 5
• Steps 5 Rooms: 4
• Steps 6 Rooms: 2
• Steps 7 Rooms: 1
• Steps 8 Rooms: 0
• Steps 9 Rooms: 0
• Steps 10 Rooms: 0

Expected Output:
Shortest path to d : 10

• Steps 0 Rooms: 1
• Steps 1 Rooms: 2
• Steps 2 Rooms: 3
• Steps 3 Rooms: 4
• Steps 4 Rooms: 4
• Steps 5 Rooms: 3
• Steps 6 Rooms: 2
• Steps 7 Rooms: 2
• Steps 8 Rooms: 1
• Steps 9 Rooms: 0
• Steps 10 Rooms: 1

Essentially, what the tree will generate will be all the possible ways to reach all of the rooms if it is reachable. And by doing a BFS on the tree, and tracking all previous visited rooms, I can find the shortest path to every reachable room.