二刷 07/2022
Version #1 BFS
关键是BFS不仅是带坐标的而且是带状态的
Time O(MN)
Space O(MN)
Runtime: 128 ms, faster than 63.11% of Java online submissions for Shortest Path to Get All Keys.
Memory Usage: 64.9 MB, less than 40.78% of Java online submissions for Shortest Path to Get All Keys.
class Solution {
class State {
int y, x;
int keys;
public State(int y, int x, int keys) {
this.y = y;
this.x = x;
this.keys = keys;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof State)) {
return false;
}
State s = (State) o;
return this.y == s.y && this.x == s.x && this.keys == s.keys;
}
@Override
public int hashCode() {
return Objects.hash(this.y, this.x, this.keys);
}
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
public int shortestPathAllKeys(String[] grid) {
Queue<State> que = new ArrayDeque<>();
int wantKeys = 0;
Set<State> visited = new HashSet<>();
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length(); x++) {
char c = grid[y].charAt(x);
if (c == '@') {
State s = new State(y, x, 0);
que.offer(s);
visited.add(s);
}
if (c >= 'a' && c <= 'z') {
wantKeys |= 1 << (c - 'a');
}
}
}
if (wantKeys == 0) {
return 0;
}
int step = 0;
while (!que.isEmpty()) {
int size = que.size();
step++;
while (size-- > 0) {
State curr = que.poll();
for (int i = 0; i < 4; i++) {
int ny = curr.y + dy[i];
int nx = curr.x + dx[i];
int key = curr.keys;
if (ny < 0 || nx < 0 || ny >= grid.length || nx >= grid[0].length()) {
continue;
}
char c = grid[ny].charAt(nx);
if (c == '#') {
continue;
}
if (c >= 'A' && c <= 'Z') {
if ((curr.keys & (1 << (c - 'A'))) == 0) {
continue;
}
}
if (c >= 'a' && c <= 'z') {
key |= 1 << (c - 'a');
if (key == wantKeys) {
return step;
}
}
State ns = new State(ny, nx, key);
if (!visited.add(ns)) {
continue;
}
que.offer(ns);
}
}
}
return -1;
}
}
This problem is 'different' and 'similar' to the problem -> shortest path to visit all nodes in the graph
For that question, all previously visited node and current position made up the state, so we need to somehow hash all the visited nodes by bit manipulation
-> Here, we only care about how many keys have we picked up
So we only care about the current position and how many keys have we picked up
One important knowledge here is how to override hash and equals for self-defined classes
86.70 %
class Solution {
class State {
int keys, y, x;
public State(int keys, int y, int x) {
this.keys = keys;
this.y = y;
this.x = x;
}
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof State)) {
return false;
}
State state = (State) o;
return this.keys == state.keys && this.y == state.y && this.x == state.x;
}
@Override
public int hashCode() {
return Objects.hash(keys, y, x);
}
@Override
public String toString() {
return Integer.toBinaryString(keys) + " " + y + " " + x;
}
}
public static void main(String[] args) {
}
// 1 2 3 4 5 6
// a b c d e f
public int shortestPathAllKeys(String[] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length() == 0) return 0;
int rows = grid.length;
int cols = grid[0].length();
int targetKeys = 0;
Queue<State> que = new LinkedList<>();
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
char c = grid[y].charAt(x);
if (c == '@') {
que.offer(new State(0, y, x));
} else if (c >= 'a' && c <= 'f') {
targetKeys |= 1 << (c - 'a');
}
}
}
Set<State> visited = new HashSet<>();
int[] dx = new int[]{1, 0, -1, 0};
int[] dy = new int[]{0, -1, 0, 1};
int steps = 0;
while (!que.isEmpty()) {
int size = que.size();
steps++;
while (size-- > 0) {
State curr = que.poll();
// System.out.println(curr.toString());
for (int i = 0; i < 4; i++) {
int nextX = curr.x + dx[i];
int nextY = curr.y + dy[i];
if (nextX < 0 || nextX >= cols || nextY < 0 || nextY >= rows) {
continue;
}
char c = grid[nextY].charAt(nextX);
int keys = curr.keys;
if (c == '#' || (c >= 'A' && c <= 'F' &&
(keys & (1 << (c - 'A'))) == 0)) { // wall or don't have the key
continue;
}
if (c >= 'a' && c <= 'f') { // found a key
keys |= 1 << (c - 'a');
if (keys == targetKeys) {
return steps;
}
}
State nextState = new State(keys, nextY, nextX);
if (visited.add(nextState)) {
que.offer(nextState);
}
}
}
}
return -1;
}
}
No comments:
Post a Comment