В настоящее время у меня есть задание, где вам дан лабиринт, состоящий из rx c Room. В комнате по краям лабиринта есть стены, представляющие края лабиринта, поэтому вы не можете пройти через комнаты по краям.
Данная проблема заключается в том, что вы получили возможность разрушать стены в лабиринте, и вы можете использовать его заданные k раз в лабиринте. Функция public Integer pathSearch(int startRow, int startCol, int endRow, int endCol, int superpowers) должна найти кратчайший путь от заданной начальной точки до комнаты назначения.
Также необходимо отслеживать количество комнат, достижимых в данном кратчайшем номере пути для запроса numsReachable, который будет возвращать целое число, указывающее, сколько существует комнат, так что минимальное количество количество шагов, необходимых для его достижения, k, исходя из вашего самого последнего pathSearch начального местоположения.
Моя текущая идея состоит в том, чтобы сгенерировать дерево пространства состояний для заданной начальной комнаты и мощности. Каждая вершина в дереве представляет собой состояние, которое представляет собой комбинацию Room координат и количества оставшихся степеней. Края дерева представляют прыжок из одной комнаты в соседнюю комнату, если она существует. Если соседняя комната отделена стеной, то переход из состояния, например. Комната (1,1) в комнату (1,2) приведет к снижению мощности.
После того, как я сгенерировал данное дерево, я бы сделал BFS для дерева и для каждой границы при заданном количестве прыжков я бы оставил его в списке с указанным индексом, представляющим число прыжков, размер границы, представляющий количество достижимых комнат.
Вот код для рекурсивного построения дерева.
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);
}
}
Я выбрасываю неправильное количество комнат, скорее всего, потому что мое построение дерева не работает должным образом. Тем не менее, после тестирования в течение нескольких дней я все еще не мог найти ошибку в моем логе c или коде. Есть ли понимание того, что можно сделать, чтобы изменить его?
Редактировать: Для pathSearch он вернет кратчайший путь из начальной комнаты в комнату назначения.
Если возвращаемое значение:
- 0 - пункт назначения является начальным местоположением
- null - указывает, что пункт назначения не доступен ни по одному пути, учитывая количество степеней
Для метода numsReachable он должен возвращать все возможные комнаты, достигаемые в точности с указанным количеством прыжков. Если количество прыжков превысит максимальное количество минимальных прыжков, необходимых для достижения каждой комнаты, то он вернет 0;
Учитывая этот лабиринт:
- ┏━━━┳━━━━━━━┳━━━┳━━━┓
- ┃ ┃ ┃ ┃ s ┃
- ┃ ┃ ╻ ┃ ╹ ┃
- ┃ ┃ ┃ ┃ ┃
- ┣━━━╋━━━┻━━━╋━━━┓ ┃
- ┃ d ┃ ┃ ┃ ┃
- ┣━━━╋━━━┓ ┃ ┃ ┃
- ┃ ┃ ┃ ┃ ┃ ┃
- ┃ ┃ ┃ ┣━━━┛ ┃
- ┃ ┃ ┃ ┃ ┃
- ┗━━━┻━━━┻━━━┻━━━━━━━┛
Учитывая начальную координату: Комната в (0,4) указано «s».
Назначение: Комната в (2,0) обозначена «d».
Количество разрешенных полномочий: 2.
Это требуется 10 шагов для достижения d из s
Однако проблема в том, что число номеров, достижимых при k шагах, неверно. Это мой вывод: Кратчайший путь к d: null
- Этапы 0 Комнаты: 1
- Этапы 1 Комнаты: 2
- Этапы 2 Комнаты: 4
- Steps 3 Rooms: 6
- Steps 4 Rooms: 5
- Steps 5 Rooms: 4
- Steps 6 Rooms: 2
- Steps 7 Rooms : 1
- Этапы 8 номеров: 0
- Этапы 9 номеров: 0
- Этапы 10 номеров: 0
Ожидаемый результат: Кратчайший путь к д: 10
- Steps 0 Rooms: 1
- Steps 1 Rooms: 2
- Steps 2 Rooms: 3
- Steps 3 Rooms: 4
- Этапы 4 номера: 4
- Этапы 5 номера: 3
- Этапы 6 номера: 2
- Этапы 7 номера: 2
- Шаги 8 Комнаты: 1
- Шаги 9 Комнаты: 0
- Шаги 10 Комнаты: 1
По сути, то, что дерево сгенерирует, будет всеми возможными способами достичь всех комнат, если это достижимо. И, выполнив BFS на дереве и отслеживая все предыдущие посещенные комнаты, я могу найти кратчайший путь к каждой достижимой комнате.