Skip to content

Instantly share code, notes, and snippets.

@0xhmn
Created March 6, 2021 22:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save 0xhmn/370b6c798cdf688263160326466896c3 to your computer and use it in GitHub Desktop.
Save 0xhmn/370b6c798cdf688263160326466896c3 to your computer and use it in GitHub Desktop.
public class MinPathWithOneFlip {
/**
* [x,y,flip,dist] -> we can get to i=2,j=0 in two different ways: [2,0,1,1] && [2,0,0,8]
* we should keep track of two different scenarios. if we have flipped and reached there or if we reached there with no flip
*/
int[][] DIR = {{1,0}, {0,1}, {-1,0}, {0,-1}};
int minPath(int[][] board) {
int m = board.length;
int n = board[0].length;
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[3] - o2[3]);
pq.add(new int[]{0,0,0,0});
// we split the hash into two cases for each entry: x + y + flipStatus
// "0:0:0" -> x is 0, y is 0 and not flipped
// Hash to Distance
Map<String, Integer> map = new HashMap<>();
map.put("0:0:0", 0);
while(!pq.isEmpty()) {
int[] front = pq.poll();
int x = front[0];
int y = front[1];
int flip = front[2];
int dist = front[3];
String hash = x + ":" + y + ":" + flip;
if (x == m - 1 && y == n - 1) {
return dist;
}
if (map.containsKey(hash) && map.get(hash) < dist) {
continue;
}
for (int[] dir : DIR) {
int nx = x + dir[0];
int ny = y + dir[1];
int nd = dist + 1;
if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
continue;
}
int val = board[nx][ny];
String noFlipHash = nx + ":" + ny + ":" + 0;
String flipHash = nx + ":" + ny + ":" + 1;
if (val == 0) {
if (!map.containsKey(noFlipHash) || (map.containsKey(noFlipHash) && map.get(noFlipHash) > nd)) {
pq.add(new int[]{nx, ny, flip, nd});
map.put(noFlipHash, nd);
}
// if we can reach to this node from a flipped path
if (map.containsKey(flipHash) && map.get(flipHash) > nd) {
pq.add(new int[]{nx, ny, 1, nd});
map.put(flipHash, nd);
}
}
if (val == 1) {
if (flip == 1) {
// no more flip is allowed
continue;
} else if (!map.containsKey(flipHash)) {
// we can flip this node
pq.add(new int[]{nx, ny, 1, nd});
map.put(flipHash, nd);
} else if (map.containsKey(flipHash) && map.get(flipHash) > nd) {
// we can improve
pq.add(new int[]{nx, ny, 1, nd});
map.put(flipHash, nd);
}
}
}
}
return -1;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment