Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:


	1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
	2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
	3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
	4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])


Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with cost = 1. 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.

&nbsp;
Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --&gt; (0, 1) --&gt; (0, 2) --&gt; (0, 3) change the arrow to down with cost = 1 --&gt; (1, 3) --&gt; (1, 2) --&gt; (1, 1) --&gt; (1, 0) change the arrow to down with cost = 1 --&gt; (2, 0) --&gt; (2, 1) --&gt; (2, 2) --&gt; (2, 3) change the arrow to down with cost = 1 --&gt; (3, 3)
The total cost = 3.


Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).


Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 100
	1 &lt;= grid[i][j] &lt;= 4


class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        changes = [[float("inf") for _ in range(len(grid[0]))] for _ in range(len(grid))]
        heap = [(0,0,0)]
        dirn = [(0,1),(0,-1),(1,0),(-1,0)]
        while heap:
            dist,r,c = heapq.heappop(heap)
            if r >= len(grid) or r < 0 or c >= len(grid[0]) or c < 0 or changes[r][c] <= dist:
                continue
            if r == len(grid) - 1 and c == len(grid[0]) - 1:
                return dist
            changes[r][c] = dist
            for i in range(1,5):
                if i == grid[r][c]:
                    heapq.heappush(heap,(dist,r+dirn[i-1][0],c+dirn[i-1][1]))
                else:
                    heapq.heappush(heap,(dist+1,r+dirn[i-1][0],c+dirn[i-1][1]))
        return dist
                    
class Solution {

    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

    private boolean isValid(int i,int j,int n,int m) {
        return i<n && j<m && i>=0 && j>=0;
    }

    private boolean isValidDirection(int [][]grid,int []currEle,int nx,int ny) {
        int nextX=currEle[0],nextY = currEle[1];
        int n =grid.length,m = grid[0].length;

        switch(grid[currEle[0]][currEle[1]]) {
            case 1: nextY++; break;
            case 2: nextY--; break;
            case 3: nextX++; break;
            case 4: nextX--; break;
        }

        return nextX==nx && nextY==ny;
    }

    public int minCost(int[][] grid) {

        int n = grid.length;
        int m = grid[0].length;

        int dist[][] = new int[n][m];
        boolean vis[][] = new boolean[n][m];

        LinkedList<int[]> queue = new LinkedList<>(); // for performing 01 BFS

        for(int i=0;i<n;i++)
            Arrays.fill(dist[i],Integer.MAX_VALUE);

        queue.add(new int[]{0,0});
        dist[0][0]=0;

        while(!queue.isEmpty()) {

            int[] currEle = queue.remove();
            vis[currEle[0]][currEle[1]] = true;

            for(int[] currDir:dirs) {

                    int nx = currDir[0]+currEle[0];
                    int ny = currDir[1]+currEle[1];
                    if(isValid(nx,ny,n,m) && vis[nx][ny]==false) {

                        if(isValidDirection(grid,currEle,nx,ny)) {
                            dist[nx][ny] = Math.min(dist[nx][ny],dist[currEle[0]][currEle[1]]);
                            queue.add(0,new int[]{nx,ny});
                        }
                        else {
                        dist[nx][ny] = Math.min(dist[nx][ny],1+dist[currEle[0]][currEle[1]]);
                            queue.add(new int[]{nx,ny});
                        }
                    }
            }

        }

       return dist[n-1][m-1];
    }
}
#define vv vector<int>

class Solution {
public:

    int dx[4]={0 , 0, 1 , -1};
    int dy[4]={1 , -1 , 0 , 0};

    int minCost(vector<vector<int>>& grid) {

        int m=grid.size();
        int n=grid[0].size();

        priority_queue< vv , vector<vv> , greater<vv>> pq;

        vector<vector<int>> dp(m+3 , vector<int>(n+3 , INT_MAX));

        dp[0][0]=0;
        pq.push({0 , 0 , 0});

        // there is no need of visited

        // distance or u can say cost relaxation

        while(!pq.empty())
        {

            auto v=pq.top();
            pq.pop();

            int cost=v[0];
            int i=v[1];
            int j=v[2];

            if(i==m-1 && j==n-1)
            {
                return cost;
            }

            for(int k=0;k<4;k++)
            {
                int newi=i+dx[k];
                int newj=j+dy[k];

                if(newi>=0 && newj>=0 && newi<m && newj<n)
                {
                    if((k+1)==grid[i][j])
                    {
                        if(dp[newi][newj]>cost)
                        {
                            dp[newi][newj]=cost;
                            pq.push({cost , newi , newj});
                        }
                    }
                    else
                    {
                        if(dp[newi][newj]>cost+1)
                        {
                            dp[newi][newj]=cost+1;
                            pq.push({cost+1 , newi , newj});
                        }
                    }
                }
            }

        }

        if(dp[m-1][n-1]!=INT_MAX)
        {
            return dp[m-1][n-1];
        }

        return -1;

    }
};
const minCost = function (grid) {
	const m = grid.length,
		n = grid[0].length,
		checkPos = (i, j) =>
			i > -1 && j > -1 && i < m && j < n && !visited[i + "," + j],
		dir = { 1: [0, 1], 2: [0, -1], 3: [1, 0], 4: [-1, 0] },
		dfs = (i, j) => {
			if (!checkPos(i, j)) return false;
			if (i === m - 1 && j === n - 1) return true;
			visited[i + "," + j] = true;
			next.push([i, j]);
			return dfs(i + dir[grid[i][j]][0], j + dir[grid[i][j]][1]);
		},
		visited = {};
	let changes = 0, cur = [[0, 0]], next;
	while (cur.length) {
		next = [];
		for (const [i, j] of cur) if (dfs(i, j)) return changes;
		changes++;
		cur = [];
		next.forEach(pos => {
			for (let d = 1; d < 5; d++) {
				const x = pos[0] + dir[d][0],
					y = pos[1] + dir[d][1];
				if (checkPos(x, y)) cur.push([x, y]);
			}
		});
	}
};
Minimum Cost to Make at Least One Valid Path in a Grid