minPaht.java

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;
    }
}