# (01 BFS) 1368. Minimum Cost to Make at Least One Valid Path in a Grid

T: O(ElogV), E = 4mn, V = mn

S: O(mn)

```java
class Solution {
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1, 0}, {-1, 0}}; // 1,2,3,4

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // small cost first
        pq.offer(new int[]{0, 0 , 0});
        visited[0][0] = true;
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0];
            int curX = cur[1];
            int curY = cur[2];
            
            if (curX == m - 1 && curY == n - 1) {
                return cost;
            }
            
            for (int i = 0; i < 4; i++) {
                int x = curX + DIRS[i][0];
                int y = curY + DIRS[i][1];
                if (!isValid(m, n, x, y) || visited[x][y]) {
                    continue;
                }
                int addOn = (i+1 == grid[curX][curY]) ? 0 : 1; // is change dir?
                pq.offer(new int[]{cost + addOn, x, y});
                visited[x][y] = true;
            }
        }
        return -1;
    }
    private boolean isValid(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

/*
1 => j+1 right
2 => j-1 left
3 => i+1
4 => i-1

The valid path does not have to be the shortest.


You can modify the sign on a cell one time only.


Return the minimum cost to make the grid have at least one valid path.

[
[1,1,3],   -> -> d
[3,2,2],   d. <- <-
[1,1,4]    -> -> u 
]

*/
```

### Latest

T: O(mn)

S: O(mn)

因為其實只會有兩種 cost, 原本的cost 和另一種 cost+1, 所以可以用一個 queue 即可, cost不變的放前面, cost +1 的放後面, 這樣省去用 pq

所以 time complexity 變成 O(mn)

```java
class Solution {
private int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 0-based, 1 -> 0
    
    private record Result(int x, int y, int cost){};

    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        Deque<Result> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[m][n];
        queue.offer(new Result(0, 0, 0)); // 

        while (!queue.isEmpty()) {
            Result cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int cost = cur.cost;

            if (visited[x][y]) { 
                continue;
            }
            visited[x][y] = true; 
            if (x == m-1 && y == n-1) {
                return cost;
            }
            for (int[] dir : DIRECTIONS) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (DIRECTIONS[grid[x][y]-1].equals(dir)) {
                    queue.offerFirst(new Result(nx, ny, cost)); // 1,2-1 = 1,1
                } else {
                    queue.offer(new Result(nx, ny, cost+1)); // 1,2-1 = 1,1
                }
            }
        }
        return 0;
    }
}

/*
1 => j+1 right
2 => j-1 left
3 => i+1
4 => i-1

The valid path does not have to be the shortest.


You can modify the sign on a cell one time only.


Return the minimum cost to make the grid have at least one valid path.

[
[1,1,3],   -> -> d
[3,2,2],   d. <- <-
[1,1,4]    -> -> u 
]

*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/01-bfs/01-bfs-1368.-minimum-cost-to-make-at-least-one-valid-path-in-a-grid.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.